leetcode 759 - Employee Free Time

https://leetcode.com/problems/employee-free-time/

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined). Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren’t finite.
Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]

Constraints:

1 <= schedule.length , schedule[i].length <= 50
0 <= schedule[i].start < schedule[i].end <= 10^8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*
// Definition for an Interval.
class Interval {
public:
int start;
int end;

Interval() {}

Interval(int _start, int _end) {
start = _start;
end = _end;
}
};
*/
class Solution {
public:
vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
vector<Interval> all;

for (auto &s : schedule)
for (auto &i : s)
all.push_back(i);

auto mycomp = [](const Interval &i1, const Interval &i2) {
return i1.start < i2.start;
};
sort(all.begin(), all.end(), mycomp);

vector<Interval> merged = merge(all);

vector<Interval> result;
for (int i = 1; i < merged.size(); i++)
result.push_back(Interval(merged[i-1].end, merged[i].start));

return result;
}

vector<Interval> merge(vector<Interval> &all) {
vector<Interval> result;

result.push_back(all[0]);

for (int i = 1; i < all.size(); i++) {
if (all[i].start <= result.back().end)
result.back().end = max(result.back().end, all[i].end);
else
result.push_back(all[i]);
}

return result;
}
};

//Line sweep
class Solution {
public:
#define START 1
#define END 2

vector<Interval> employeeFreeTime(vector<vector<Interval>> schedule) {
vector<pair<int,int>> events;

for (auto &s : schedule) {
for (auto &i : s) {
events.push_back({i.start, START});
events.push_back({i.end, END});
}
}

auto mycomp = [](const pair<int, int> &e1, const pair<int, int> &e2) {
if (e1.first == e2.first) return e1.second < e2.second;
return e1.first < e2.first;
};

sort(events.begin(), events.end(), mycomp);

int prev = -1;
int balance = 0;
vector<Interval> results;

for (auto &e : events) {
if (balance == 0 && prev != -1)
results.push_back(Interval(prev, e.first));
balance += (e.second == START ? 1 : -1);
prev = e.first;
}

return results;
}
};