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
The solution involves merging all intervals and then finding the free time between them.
public int[][] findFreeTime(int[][][] intervals) {
List<int[]> allIntervals = new ArrayList<>();
for (int i = 0;
i < intervals.length;
i++) {
for (int j = 0;
j < intervals[i].length;
j++) {
allIntervals.add(intervals[i][j]);
}
}
Collections.sort(allIntervals, (a, b) -> a[0] - b[0]);
List<int[]> merged = new ArrayList<>();
merged.add(allIntervals.get(0));
for (int i = 1;
i < allIntervals.size();
i++) {
if (merged.get(merged.size() - 1)[1] >= allIntervals.get(i)[0]) {
merged.get(merged.size() - 1)[1] = Math.max(merged.get(merged.size() - 1)[1], allIntervals.get(i)[1]);
}
else {
merged.add(allIntervals.get(i));
}
}
List<int[]> freeTime = new ArrayList<>();
for (int i = 0;
i < merged.size() - 1;
i++) {
if (merged.get(i)[1] < merged.get(i + 1)[0]) {
freeTime.add(new int[] {
merged.get(i)[1], merged.get(i + 1)[0]}
);
}
}
return freeTime.toArray(new int[freeTime.size()][]);
}
Follow-up:
What if the intervals are not sorted?