Train Speed for a Deadline

Medium

To reach your destination you ride several trains one after another. The array legs holds the length of each leg in kilometers: legs[i] is the distance covered by train i. You have deadline hours. Every train runs at the same integer speed v km/h, so a leg of length d takes d / v hours. Trains only depart on the hour, though: if you reach a transfer at, say, the 2.4-hour mark, the next train leaves at 3. There is no waiting after the last train. Return the smallest positive integer speed v that gets you there no later than deadline. If no speed is fast enough, return -1.

Example 1

legs=[4, 2, 6], deadline=7.0 → 2

At speed 2 the first train takes 2 hours, the second 1 hour and the third 3 hours: 6 hours in total. Speed 1 would take 12 hours.

Example 2

legs=[3, 5], deadline=1.5 → 10

The second train cannot leave before the 1-hour mark, which leaves half an hour for 5 km, so speed 10 is needed. At that speed the first train finishes in 0.3 hours.

Example 3

legs=[1, 1, 1], deadline=2.0 → -1

The third train cannot depart before the 2-hour mark, which is already the deadline. It is impossible.

Constraints

1 ≤ len(legs) ≤ 10⁵
1 ≤ legs[i] ≤ 10⁵
1 ≤ deadline ≤ 10⁹, with at most two digits after the decimal point
Whenever an answer exists, it is at most 10⁷

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Binary Search