[LeetCode]Employee Free Time

这道题本质上就是给定一堆的intervals，让我们不找被interval覆盖的区间。解法的话也很直接，我们可以直接把所有intervals按照start time sort，然后用类似Meeting Rooms II的解法，用一条线从左向右扫描，找到没有interval的区间，假设有k个员工，平均每个人有n个interval，时间复杂度O(n* k * log (n * k))，空间复杂度O(n * k)，代码如下：

	/**
	* Definition for an interval.
	* struct Interval {
	* int start;
	* int end;
	* Interval() : start(0), end(0) {}
	* Interval(int s, int e) : start(s), end(e) {}
	* };
	*/
	class Solution {
	public:
	vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
	int len = schedule.size();
	vector<pair<int, int>> events;
	for(auto& v : schedule)
	{
	for(auto& i : v)
	{
	events.push_back(make_pair(i.start, 0));
	events.push_back(make_pair(i.end, 1));
	}
	}
	sort(events.begin(), events.end());
	vector<Interval> res;
	int count = 0, start = -1;
	for(auto& event : events)
	{
	if(event.second == 1)
	{
	--count;
	if(!count)start = event.first;
	}
	else
	{
	if(!count && start != -1)res.push_back(Interval(start, event.first));
	++count;
	}
	}
	return res;
	}
	};

view raw Employee Free Time_line_sweep.cpp hosted with ❤ by GitHub

此外我们用merge k sorted lists的解法也可以，时间复杂度O(n * k * log n)，空间复杂度O(n)，代码如下：

	/**
	* Definition for an interval.
	* struct Interval {
	* int start;
	* int end;
	* Interval() : start(0), end(0) {}
	* Interval(int s, int e) : start(s), end(e) {}
	* };
	*/
	class Solution {
	public:
	vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
	int len = schedule.size();
	auto comp = [&](const pair<int, int>& lhs, const pair<int, int>& rhs)
	{
	Interval i1 = schedule[lhs.first][lhs.second], i2 = schedule[rhs.first][rhs.second];
	return i1.start == i2.start? i1.end < i2.end: i1.start > i2.start;
	};
	priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(comp)> pq(comp);
	for(int i = 0; i < len; ++i)pq.push(make_pair(i, 0));
	vector<Interval> res;
	int busyUntil = -1;
	while(pq.size())
	{
	auto p = pq.top();
	pq.pop();
	Interval curr = schedule[p.first][p.second];
	if(busyUntil == -1)busyUntil = curr.end;
	else
	{
	if(curr.start > busyUntil)res.push_back(Interval(busyUntil, curr.start));
	busyUntil = max(busyUntil, curr.end);
	}
	if(p.second + 1 < schedule[p.first].size())
	pq.push(make_pair(p.first, p.second + 1));
	}
	return res;
	}
	};

view raw Employee Free Time_pq.cpp hosted with ❤ by GitHub