FastPrep
Problem · Array

Minimum Bridge Turnbacks

Learn this problem
● MediumBNSF Railway logoBNSF RailwayFULLTIMEOA

Problem statement

A line of cars approaches a one-way bridge in the order given by the integer array weight. The bridge supports at most a total weight of U, and at most two cars can be on it at the same time.

Cars enter and leave in their original relative order. Before a car enters, its driver may be told to turn back. That car is then removed permanently, while every remaining car keeps its relative position.

Choose which drivers turn back so that the bridge is never overloaded. Equivalently, every retained car must weigh at most U, and every two consecutive retained cars must have a combined weight of at most U.

Return the minimum number of drivers who must turn back.

Function

solution(U: int, weight: int[]) → int

Examples

Example 1

U = 9weight = [5,3,8,1,8,7,7,6]return = 4

One optimal choice keeps the cars with weights [5,3,1,6]. Its consecutive sums are 8, 4, and 7, all at most 9. Four drivers turn back.

More BNSF Railway problems

drafts saved locally
public int solution(int U, int[] weight) {
    // Write your code here.
}
U9
weight[5,3,8,1,8,7,7,6]
expected4
checking account