Total Questions - 2 Algorithimic
Imagine a horizontal line where ubers are standing parlallel to the line. Each uber has a coordinate [l, r].
Given a list of coordinates find the markers where there is atleast one uber standing.
A marker is a point on a horizontal line.Input: coordinates = [[3,6], [-1,5],[4,7]
Output: 9
Explanation: Markers at 2 0, -1, 7, 6, 5, 4, 3, 1 have atleast one uberFor every uber coordinate given there always exits atleast one uber in that range inclusively.
We should just avoid over counting the same range.
For example [-1, 5] and [3,6 ] we should avoid counting [3,5] again. So we just merge all the coordinates.
For each merged coordinate [start, end] the no. of markers = end - start + 1; Given a list of cabTripTimes which indicates that cab i takes cabTripTimes[i] time to complete one trip.
Find the min time it takes to complete n trips. At time t we can start multiple trips.
Assume there is no buffer in between starting trips again.Input: cabTripTimes = [1,2], n = 3
Output: 2
Explanation:
At time t = 0; start trips 1, 2
At time t = 1; end trip 1, and start trip 1.
At time t = 2; end trip 2, end trip 1,
Earliest time to end 3 trips is 2.Used a PriorityQueue of pairs which had endTime and tripTime of a cab with min endTime as priority.
Start a loop from time = 1. pop all the elements from the queue which have the same endTime as time and decrement n for each pop.
Add each pair back to the queue with endTime = endTime + tripTime.
Break loop when n == 0 and return time.All Test cases passed for both the solutions. I really tried to get a Math solution for Q2. I would appreciate to get any other improved approach than what I tried. Thanks