Employee Free Time
Given a list of intervals representing the busy time of 'N' employees, find out if there is a possibility of free time when there are no meetings.
Constraints:
- 1 <= N <= 10
- 1 <= intervals.length <= 100
- intervals[i].length == 2
Examples:
Input: [[[1,3],[6,7]],[[2,4]],[[8,9]]]
Output: [[3,6]]
Explanation: The free time is between 3 to 6.
Solutions
Merging Intervals
Time: O(N log N)Space: O(N)
The solution involves merging all intervals and then finding the free time between them.
vector<vector<int>> findFreeTime(vector<vector<vector<int>>>& intervals) {
vector<vector<int>> allIntervals;
for (auto& i : intervals) {
for (auto& j : i) {
allIntervals.push_back(j);
}
}
sort(allIntervals.begin(), allIntervals.end(), [](vector<int>& a, vector<int>& b) {
return a[0] < b[0];
}
);
vector<vector<int>> merged = {
allIntervals[0]}
;
for (int i = 1;
i < allIntervals.size();
i++) {
if (merged.back()[1] >= allIntervals[i][0]) {
merged.back()[1] = max(merged.back()[1], allIntervals[i][1]);
}
else {
merged.push_back(allIntervals[i]);
}
}
vector<vector<int>> freeTime;
for (int i = 0;
i < merged.size() - 1;
i++) {
if (merged[i][1] < merged[i + 1][0]) {
freeTime.push_back({
merged[i][1], merged[i + 1][0]}
);
}
}
return freeTime;
}Follow-up:
What if the intervals are not sorted?
