Finding unique events in the calendar [reviewed]
Problem
Find the maximum number of non-intersecting events in a Calender
For example. given list of events each of which contains start date and end date as below:
{ [1,6], [1, 3], [1, 4], [5, 6] , [6,10], [9,10], [17,18] }.
In this case, choosing the following events produce the maximum non-intersecting events.
{ [1, 3], [5, 6], [9,10], [17, 18] }
Therefore, 4 should be returned.
This problem is quite similar to the "Counting rooms" problem. However, it is simpler than that problem in that we just need to choose the event that maximize the total number of unique events.
Let's look at the following example.
As we can see in Figure 1, among the overlapping events, we need to choose the one finishing earliest to increase the possibility to choose non-intersecting events following next.
We can use the Greedy algorithm to choose the events finishing earliest but non-intersecting with the preceding event.
Here is the rough algorithm
1) Sort the events by end time so that we can select the event ending earliest each time.
2) Iterate over the events and count only unique event.
Each time we encounter the unique event, move the prev pointer to the new unique event.
3) return the count of unique events.
Overall running time of this algorithm will be $O (N \log N)$ due to the initial sorting in the step 1.
Here is the complete algorithm in C++.
Practice statistics:
05:05: to come up with the algorithm
13:00: to write up the code
UPDATE(2019-07-26): solved the problem again and could think of a correct greedy algorithm.
Here is the python solution:
Statistics:For example. given list of events each of which contains start date and end date as below:
{ [1,6], [1, 3], [1, 4], [5, 6] , [6,10], [9,10], [17,18] }.
In this case, choosing the following events produce the maximum non-intersecting events.
{ [1, 3], [5, 6], [9,10], [17, 18] }
Therefore, 4 should be returned.
This problem is quite similar to the "Counting rooms" problem. However, it is simpler than that problem in that we just need to choose the event that maximize the total number of unique events.
Let's look at the following example.
 |
| Figure 1. Sample events |
Greedy Algorithm approach
As we can see in Figure 1, among the overlapping events, we need to choose the one finishing earliest to increase the possibility to choose non-intersecting events following next.
We can use the Greedy algorithm to choose the events finishing earliest but non-intersecting with the preceding event.
Here is the rough algorithm
1) Sort the events by end time so that we can select the event ending earliest each time.
2) Iterate over the events and count only unique event.
Each time we encounter the unique event, move the prev pointer to the new unique event.
3) return the count of unique events.
 |
| Figure 2. Greedy algorithm approach |
Overall running time of this algorithm will be $O (N \log N)$ due to the initial sorting in the step 1.
Here is the complete algorithm in C++.
Practice statistics:
05:05: to come up with the algorithm
13:00: to write up the code
UPDATE(2019-07-26): solved the problem again and could think of a correct greedy algorithm.
Here is the python solution:
- 15:00 to come up with wrong algorithm and code
- could not find the algorithm using greedy
- 10:00: to write the code.
Comments
Post a Comment