Meeting Rooms
You are given a list intervals, where intervals[i] = [start, end] is the time of the i-th meeting. Return true if one person can attend all the meetings, which is the case when no two meetings overlap. Return false otherwise.
Two meetings overlap when they are both going on at some moment. A meeting that ends at time t and another that starts at time t do not overlap. An empty list can be attended.
Examples
Input intervals = [[0, 30], [5, 10], [15, 20]]
Output false
The meeting [5, 10] is inside [0, 30].
Input intervals = [[7, 10], [2, 4]]
Output true
Input intervals = [[1, 5], [5, 8]]
Output true
One ends exactly when the other starts.
Constraints
- 0 <= intervals.length <= 10,000
- intervals[i] = [start, end] with 0 <= start < end <= 1,000,000
Stuck? Take one hint at a time
Common mistakes
- Using "<=" and so treating back to back meetings as a conflict.
- Not sorting, and comparing only neighbors in the given order.
- Sorting by end time and checking each start against the previous end. It also works, but the proof is harder to say aloud than the sort by start argument, so prefer sorting by start.
- Crashing on an empty list when reading the first meeting. The empty list can be attended.
- Modifying the input list by sorting it in place when the caller still needs the original order.
Questions an interviewer may ask next
- Find the minimum number of rooms needed so that all the meetings can happen. (Meeting Rooms II: a heap of end times, or sorted starts and ends.)
- Return the pair of meetings that conflict, not only whether there is a conflict.
- Meetings come in one at a time and you must accept or reject each. What structure keeps the accepted ones? (An ordered set keyed by start, checking the two neighbors.)
- What changes if a meeting that ends at t and one that starts at t are considered overlapping?
intervals
[[0,30],[5,10],[15,20]]
Expected output
false
Run checks these cases. Submit also runs hidden cases, and shows you the first one that fails.