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.
def findFreeTime(intervals):
allIntervals = []
for i in intervals:
for j in i:
allIntervals.append(j)
allIntervals.sort(key=lambda x:
x[0])
merged = [allIntervals[0]]
for i in range(1, len(allIntervals)):
if merged[-1][1] >= allIntervals[i][0]:
merged[-1][1] = max(merged[-1][1], allIntervals[i][1])
else:
merged.append(allIntervals[i])
freeTime = []
for i in range(len(merged) - 1):
if merged[i][1] < merged[i + 1][0]:
freeTime.append([merged[i][1], merged[i + 1][0]])
return freeTimeFollow-up:
What if the intervals are not sorted?
