Understanding the Problem
We are given N events, where each event has a unique start time and an end time. Our task is to find, for each event i, the next possible event j such that:
-
The start time of event j is greater than or equal to the end time of event i:
startj >= endi -
Among all such possible events, event j should have the earliest start time.
-
If no such event exists, return -1 for that event.
Approach
1. Sorting for Efficient Lookup
Since we need to quickly find the smallest start time that is greater than or equal to a given end time, we can use binary search for efficient lookup.
- Store all start times and their original indices in a separate list.
- Sort this list based on the start times.
This helps in quickly searching for the earliest valid next event using binary search.
2. Searching for the Next Event
For each event (i):
- Extract its end time.
- Perform a binary search (
lower_bound
) on the sorted list of start times to find the first event whose start time >= end time of event (i). - If a valid event is found, store its original index in the result list.
- If no such event exists, store -1.
Complexity Analysis
- Sorting start times takes O(N log N).
- Binary search (
lower_bound
) runs in O(log N) for each event, making it O(N log N) in total.
Overall Complexity:
O(N log N)
which is highly efficient.