Bridge Capacity Problem

Problem Description

There is a bridge and cars are queued up at the entry of the bridge. Each car has a weight and at once only two cars can go to the bridge. The cars enter and exit the bridge in the same order as given in the array. For example, initially the first two cars enter the bridge, then the first car leaves and the third car arrives, then second car leaves and fourth car arrives and so on. The bridge has a capacity and if the total weight the cars on the bridge exceeds that capacity, it will break. We can remove as many cars from the queue as we want and relative order of the rest of the cars will remain same. Find the minimum number of cars to remove so that the bridge doesn’t break.

Example 1

Cars' weights

[3, 5, 2, 6, 1]

Bridge capacity

8

Answer

0

Explanation

Initially:
Cars 3 and 5 enter the bridge. Combined weight: 3 + 5 = 8 (which is okay, doesn't exceed capacity).

Car 3 leaves, Car 2 enters. Now on bridge: 5 and 2. Combined weight: 5 + 2 = 7 (okay).

Car 5 leaves, Car 6 enters. Now on bridge: 2 and 6. Combined weight: 2 + 6 = 8 (okay).

Car 2 leaves, Car 1 enters. Now on bridge: 6 and 1. Combined weight: 6 + 1 = 7 (okay).

In this scenario, we didn't have to remove any cars, and the bridge never broke. So, the minimum number of cars to remove is 0.

Example 2

Cars' weights

[3, 7, 2, 6, 1]

Bridge capacity

8

Answer

1

Explanation

Initial steps:
Cars 3 and 7 enter. Weight: 3 + 7 = 10 > 8 → bridge breaks.

So, we need to remove at least one car to prevent this. Which car should we remove?

Option 1: Remove 7. Remaining sequence:

[3, 2, 6, 1]

3 and 2: 5
2 leaves, 6 enters: 2 and 6: 8
2 leaves, 1 enters: 6 and 1: 7

No breakage. Removed 1 car.

Option 2: Remove 3. Remaining sequence:

[7, 2, 6, 1]

7 and 2: 9 > 8 → breaks. Doesn’t work.

Option 3: Remove other cars. For instance, remove 2.
Sequence:

[3, 7, 6, 1]

3 and 7: 10 > 8 → breaks. Doesn’t work.

So, the best is to remove 7, resulting in removing 1 car. Hence, the minimum number is 1.

我们长期稳定承接各大科技公司如TikTok、Google、Amazon等的OA笔试代写服务，确保满分通过。如有需求，请随时联系我们。

We consistently provide professional online assessment services for major tech companies like TikTok, Google, and Amazon, guaranteeing perfect scores. Feel free to contact us if you're interested.