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.

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++.

	#include <vector>
	#include <iostream>
	#include <algorithm>
	using namespace std;
	struct event {
	int s;
	int e;
	event(int start, int end): s(start), e(end){}
	};
	bool compare(event * prev, event *next)
	{
	return prev->e < next->e;
	}
	int find_max_unique_events(vector<event*>& input)
	{
	int count = 0;
	sort(input.begin(), input.end(), compare);
	event * prev= 0;
	for (int i =0 ; i < input.size(); i++)
	{
	if (!prev)
	{
	prev = input[i];
	count++;
	} else if (prev->e < input[i]->s)
	{
	prev = input[i];
	count++;
	}
	}
	return count;
	}
	int main()
	{
	vector<event *> input;
	input.push_back(new event(5,6));
	input.push_back(new event(6,10));
	input.push_back(new event(1,6));
	input.push_back(new event(1,3));
	input.push_back(new event(1,4));
	input.push_back(new event(9,10));
	input.push_back(new event(17,18));
	input.push_back(new event(1,6));
	cout<<"max unique cout = " << find_max_unique_events(input)<<endl;
	return 1;
	}

view raw find_max_unique_events.cpp hosted with ❤ by GitHub

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:

	def compare(left, right):
	if left[1] < right[1]:
	return -1
	else:
	return 1
	class Calendar:
	def find_events(self, events):
	#sort events by end time.
	sorted_events = sorted(events, cmp=compare)
	prev = None
	result = []
	#scan sorted events and count the unique event
	for i in sorted_events:
	if prev == None:
	prev = i
	elif self.not_overlap(prev, i) == True:
	result.append(prev)
	prev = i
	if prev != None:
	result.append(prev)
	return result
	def not_overlap(self, prev, next):
	return prev[1] < next[0] or next[1] < prev[0]
	c = Calendar()
	input = [[1,6], [1, 3], [1, 4], [5, 6] , [6,10], [9,10], [17,18]]
	print("input events = {}\noutput events = {}".format(input, c.find_events(input)))

view raw facebook_find_unique_events_greedy.py hosted with ❤ by GitHub

Statistics:
 - 15:00 to come up with wrong algorithm and code
 - could not find the algorithm using greedy
 - 10:00: to write the code.