Peak Bike Demand Intervals
Updated
Problem statement
All bike bookings are known in advance. Each row of intervals is [start, end, capacity] and reserves that many bikes.
For this exercise, assume a booking occupies the half-open interval [start, end): it includes its start and excludes its end. The total demand at a time is the sum of the capacities of active bookings.
Return every maximal interval where demand equals the highest demand reached anywhere. Each result row is [peakStart, peakEnd, peakCapacity]. Return rows in increasing start-time order. Join adjacent peak intervals into one row, even if the active bookings change at their shared endpoint. Return an empty array when there are no bookings.
Function
findPeakIntervals(intervals: int[][]) → int[][]Examples
Example 1
intervals = [[1,4,2],[2,5,3],[5,7,5]]return = [[2,4,5],[5,7,5]]The demand is 2 on [1,2), 5 on [2,4), 3 on [4,5), and 5 on [5,7). The two separate peak intervals both need 5 bikes.
Example 2
intervals = [[1,3,4],[3,6,4]]return = [[1,6,4]]The first booking ends exactly when the second starts. Demand stays at 4 throughout [1,6), so the adjacent ranges become one peak interval.
Example 3
intervals = []return = []No bookings require any bikes, so there are no peak intervals.
Constraints
- For this exercise, assume
0 <= intervals.length <= 2000. - Every row has exactly
3integers. - All input values are between
0and10^9, inclusive. - Each row satisfies
0 <= start < end <= 10^9and1 <= capacity <= 10^6.
More Faire interview questions
Similar questions at other companies
- Merge Overlapping IntervalsAtlassian · PHONE SCREEN · ONSITE INTERVIEWAtlassian interview questions
- Finish Time of Fixed-Length CPU TasksGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Maximum Concurrent Processes (Bar Raiser Round)Amazon · PHONE SCREEN · ONSITE INTERVIEW
- Meeting Scheduling SystemHevo Data · ONSITE INTERVIEW
- Maximum Intervals Overlapping a Fixed-Length WindowBooking.com · ONSITE INTERVIEW
- Generate Complete Inputs for a Supplied ClassifierGeneral Motors · ONSITE INTERVIEW
- Minimum Meeting Rooms with AssignmentsUber · PHONE SCREEN · ONSITE INTERVIEWUber interview questions
- Merge IntervalsSafe Security · ONSITE INTERVIEW
- Minimum Railway PlatformsMakeMyTrip.com · ONSITE INTERVIEWMakeMyTrip.com interview questions
- Merge Overlapping IntervalsCapgemini · ONSITE INTERVIEWCapgemini interview questions