All problems

Minimum Speed to Arrive on Time

Medium · binary search

You must take a series of trains, one after another and in the given order. dist[i] is the length in kilometres of the i-th ride.

Every train runs at the same constant speed, a whole number of kilometres per hour that you get to choose. Trains only leave on the hour (at 0:00, 1:00, 2:00 and so on). So when a ride finishes part-way through an hour, you wait until the next whole hour to board the next train. After the last ride there is nothing to wait for. You start at 0:00, and the time that counts is the moment you step off the last train.

You must arrive within minutes minutes. Return the smallest speed that makes it, or -1 if no speed does.

Examples

Example 1

Input: dist = [1, 3, 2], minutes = 160

Output: 3

At speed 3 the first ride takes 20 minutes but you board the second train at the 1 hour mark, which takes another 60 minutes, and the last ride takes 40 minutes: 60 + 60 + 40 = 160. At speed 2 the rides need 60 + 120 + 60 = 240 minutes.

Example 2

Input: dist = [5, 4, 3], minutes = 130

Output: 18

The first two rides cost one hour each at any speed of 5 or more, leaving 10 minutes for the last ride of 3 km, which needs a speed of 18.

Example 3

Input: dist = [2, 2, 2], minutes = 100

Output: -1

The first two rides cost at least an hour each because of the waiting, which is already 120 minutes.

Constraints