Earliest Water Tank Target Time
Several pumps supply water to a tank. Each pump operates during a fixed range of minutes and adds one liter of water per minute.
Find the earliest time when the total water collected in the tank reaches the target amount.
Implement the following method:
int earliestFillMinute( List<String> pumpWindows, long targetLiters )
Parameters
pumpWindows contains the operating window of every pump.- Each window has the format
"startMinute,endMinute".
targetLiters is the required amount of water.
Return Value
- Return the earliest minute when the tank contains at least
targetLiters liters.
- Return
-1 if the target cannot be reached.
Water Collection Rules
- The tank is empty before minute
1.
- A pump operating from minute
s through minute e adds one liter during every minute in the inclusive interval [s, e].
- Water remains in the tank after it is added.
- Multiple pumps may operate during the same minute.
- At minute
t, a pump with window [s, e] has contributed max(0, min(t, e) - s + 1) liters.
- The input order of the pump windows has no special meaning.
- Repeated windows are allowed and represent separate pumps.
Input Format
- Every value in
pumpWindows contains exactly two comma-separated positive integers.
- The first integer is the starting minute and the second integer is the ending minute.
- The strings do not contain spaces.
Constraints
1 <= pumpWindows.size() <= 100,000 1 <= startMinute <= endMinute <= 1,000,000,000 1 <= targetLiters <= 100,000,000,000,000 - The total amount of collected water must be calculated using
long.
Examples
Example 1
earliestFillMinute( pumpWindows = List.of("3,6", "5,8"), targetLiters = 7 )
Output: 7
Six liters have been collected by minute 6. At minute 7, the first pump has contributed four liters and the second pump has contributed three liters. The total reaches seven liters for the first time.
Example 2
earliestFillMinute( pumpWindows = List.of("2,4", "9,9"), targetLiters = 6 )
Output: -1
The first pump can add three liters and the second pump can add one liter. Since only four liters can be collected, the target cannot be reached.
Example 3
earliestFillMinute( pumpWindows = List.of("1,3", "2,5", "4,6"), targetLiters = 8 )
Output: 5
Seven liters have been collected by minute 4. The total becomes nine liters at minute 5, making it the earliest minute when the target is reached.
Example 4
earliestFillMinute( pumpWindows = List.of("6,10", "6,8", "9,12"), targetLiters = 2 )
Output: 6
Two pumps begin operating at minute 6. Together they add two liters during that minute, so the target is reached immediately.