356. Next Interval Over
A conference has sessions listed as [start, end], and no two sessions start at the same time. For a session i, its follow-up is the session j whose start time is at least the end time of session i and is the smallest such start time. A session can be its own follow-up if it starts exactly when it ends (a zero-length session).
Return an array result where result[i] is the index of the follow-up of session i in the input array, or -1 if no session starts at or after the end of session i. Comparing each session with every other session takes O(n^2) time; use sorting and binary search to do better.
Example 1
- Input:
- intervals = [[4,6],[1,3],[7,9],[2,5]]
- Output:
- [2,0,-1,2]
- Explanation:
Session 0 ends at 6; the first start at or after 6 is 7, which is session 2. Session 1 ends at 3; the first start at or after 3 is 4, session 0. Session 2 ends at 9 and nothing starts later. Session 3 ends at 5; the first start at or after 5 is 7, session 2.
Example 2
- Input:
- intervals = [[5,5]]
- Output:
- [0]
- Explanation:
The only session starts at 5, exactly when it ends, so it is its own follow-up and the answer is [0].
Constraints
1 ≤ intervals.length ≤ 2 * 105
intervals[i] = [start, end], 0 ≤ start ≤ end ≤ 109
All start times are distinct.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n log n)
- Space
- O(n)