Bike Racing – GeeksforGeeks

A motorcycle race is being organised with N bikers. The preliminary pace and the acceleration of the bikers are given in arrays H[] and A[] respectively. A biker whose pace is L or extra is taken into account to be a quick biker. The whole pace on the monitor for each hour is calculated by including the pace of every quick biker in that hour. When the overall pace on the monitor is M km/hour or extra, the protection alarm activates. The duty is to search out the minimal variety of hours after which the protection alarm will activate.

Examples:

Enter: N = 3, M = 400, L = 120, H = {20, 50, 20}, A = {20, 70, 90}
Output: 3
Rationalization: Speeds of all of the Bikers after each hour ranging from 0
Biker1 = [20  40  60  80 100] 
Biker2 = [50 120 190 260 330]
Biker3 = [20 110 200 290 380]
Preliminary Velocity on monitor  = 0 
as a result of not one of the biker’s pace is quick sufficient.
Velocity on monitor after 1st Hour= 120
Velocity on monitor after 2nd Hour= 190+200=390
Velocity on monitor after third Hour= 260+290=550
The Alarm will begin at third Hour.

Enter: N = 2, M = 60, L = 120, H = {50, 30}, A = {20, 40}
Output: 2

Naive Strategy: A easy method is to calculate the pace of each Bike in each Hour ranging from the 0^th hour. When the overall pace on the monitor is not less than M km/hr, that’s the minimal time when the alarm will activate.

Time Complexity: O(N * max(L, M))
Auxiliary House: O(1)

Environment friendly Strategy: The issue could be solved with the assistance of the Binary Search based mostly on the next statement: 

It may be noticed that if in i^th hour whole pace on the monitor is larger than or equal to M then in (i+1)^th hour it should additionally fulfill the situation because the pace of Bikes are growing linearly with time.

Comply with the steps talked about under to implement the above concept:

• Discover the utmost and minimal required hours to activate the alarm as a result of they are going to be used as the intense values for the binary search.
• The utmost and minimal values will probably be max(L, M) and 0 respectively.
• Use the binary search over this time vary and in every iteration do the next:
  • Iterate from i = 0 to N:
    • Discover the pace of the biker at the moment.
    • If the pace of the biker at the moment is not less than L then add his pace to the pace of the monitor.
  • If the pace of the monitor is not less than M then search on the left half of the time vary. In any other case, search on the best half.
• Return the minimal time as the reply.

Beneath is the implementation of the above method.

Time Complexity: O(N * log(max(L, M)))
Auxiliary House: O(1)