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.
function findFreeTime(intervals) {
let allIntervals = [];
for (let i = 0; i < intervals.length; i++) {
for (let j = 0; j < intervals[i].length; j++) {
allIntervals.push(intervals[i][j]);
}
}
allIntervals.sort((a, b) => a[0] - b[0]);
let merged = [allIntervals[0]];
for (let i = 1; i < allIntervals.length; i++) {
if (merged[merged.length - 1][1] >= allIntervals[i][0]) {
merged[merged.length - 1][1] = Math.max(
merged[merged.length - 1][1],
allIntervals[i][1]
);
} else {
merged.push(allIntervals[i]);
}
}
let freeTime = [];
for (let i = 0; i < merged.length - 1; i++) {
if (merged[i][1] < merged[i + 1][0]) {
freeTime.push([merged[i][1], merged[i + 1][0]]);
}
}
return freeTime;
}
Follow-up:
What if the intervals are not sorted?
