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.


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]]




(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.


Note:
schedule and schedule[i] are lists with lengths in range [1, 50].
0 .

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Sorting

Data structures

Starter code: """
# Definition for an Interval.
class Interval:
    def __init__(self, start: int = None, end: int = None):
        self.start = start
        self.end = end
"""
class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        

Solutions:
class Solution:

	def intersectionSizeTwo(self, intervals):
		intervals.sort(key=lambda x: x[1])
		if len(intervals) <= 1:
			return len(intervals[0])
		s = set()
		prev_e = None
		intersect = False
		for e in intervals:
			if not s:
				a = e[1] - 1
				b = e[1]
				s.add(a)
				s.add(b)
				continue
			if e[0] <= a:
				intersect = True
				continue
			if e[0] > a and e[1] > b >= e[0]:
				intersect = True
				a = b
				b = e[-1]
				s.add(b)
				continue
			a = e[1] - 1
			b = e[1]
			s.add(a)
			s.add(b)
		if not intersect:
			return 0
		return len(s)


class Solution:

	def intersectionSizeTwo(self, intervals):
		r1 = [x[0] for x in intervals]
		r2 = [x[1] for x in intervals]
		intervals = sorted(intervals, key=lambda x: x[1])
		s = [intervals[0][1] - 1, intervals[0][1]]
		for interval in intervals:
			if interval[0] > s[-1]:
				s += [interval[1] - 1, interval[1]]
			elif interval[0] > s[-2]:
				s += [interval[1]]
		return len(s)


class Solution:

	def intersectionSizeTwo(self, intervals):
		intervals.sort(key=lambda inter: (inter[1], -inter[0]))
		res = 0
		(left, right) = (-1, -1)
		for inter in intervals:
			if inter[0] <= left:
				continue
			if inter[0] > right:
				res += 2
				right = inter[1]
				left = right - 1
			elif inter[0] <= right:
				res += 1
				left = right
				right = inter[1]
		return res


class Solution:

	def intersectionSizeTwo(self, intervals):
		intervals.sort(key=lambda x: x[1])
		if len(intervals) <= 1:
			return len(intervals[0])
		s = set()
		for e in intervals:
			if not s:
				a = e[1] - 1
				b = e[1]
				s.add(a)
				s.add(b)
				continue
			if e[0] <= a:
				continue
			if e[0] > a and e[1] > b >= e[0]:
				a = b
				b = e[-1]
				s.add(b)
				continue
			a = e[1] - 1
			b = e[1]
			s.add(a)
			s.add(b)
		return len(s)


class Solution:

	def intersectionSizeTwo(self, intervals):
		res = 0
		last2 = [-float('inf')] * 2
		intervals = sorted(intervals, key=lambda x: x[1])
		for (lo, hi) in intervals:
			n = sum((x < lo for x in last2))
			res += n
			if n == 2:
				last2 = (hi - 1, hi)
			elif n == 1:
				last2 = (last2[1], hi)
		return res