Leetcode 759. Employee Free Time

문제

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.

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

직원들의 근무 시간을 나타내는 리스트 schedule이 주어진다.

각 직원은 여러 개의 Interval 리스트를 가지고 있으며,
각 Interval은 해당 직원이 근무하는 시간을 의미한다.

각 직원의 Interval들은 서로 겹치지 않으며,
시작 시간 기준으로 정렬되어 있다.

모든 직원이 공통으로 쉬는 시간 중에서,
길이가 양수인 유한한 구간들을 정렬된 순서로 반환하라.

단, 문제에서 Interval을 [x, y] 형태로 표현하더라도,
실제로 내부 원소는 리스트나 배열이 아니라 Interval 객체이다.

예를 들어,

schedule[0][0].start = 1
schedule[0][0].end = 2

처럼 접근할 수 있지만,

schedule[0][0][0]

처럼 인덱스로 접근하는 것은 정의되어 있지 않다.

또한 [5, 5]처럼 길이가 0인 구간은 정답에 포함하지 않는다.

예시

입력: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
출력: [[3,4]]

설명:
총 세 명의 직원이 있다.

모든 직원이 공통으로 쉬는 시간 구간은 다음과 같다.

[-inf, 1], [3, 4], [10, inf]

하지만 inf를 포함하는 구간은 유한한 구간이 아니므로 버린다.

따라서 정답은 [[3,4]]이다.

제한

풀이

• 모든 사원의 겹치는 쉬는 시간을 구한다는것은 즉,
• 모든 사원의 일하는 시간을 합쳐버린다음에 쉬는시간을 구해버리면 그만이다.
• 힙을 이용해 모든 사원의 일하는 시간을 합치고, 합쳐진 리스트를 이용해 정답을 구하면 끝!

"""
# 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]':
        h = []
        table = []

        for s in schedule:
            for time in s:
                heappush(h, (time.start, time.end))

        target = None

        while h:
            if target is None:
                target = heappop(h)
                continue

            check = heappop(h)

            if target[1] >= check[0]:
                target = (target[0], max(target[1], check[1]))
            else:
                table.append(target)
                target = check

        if target is not None:
            table.append(target)

        ans = []

        for i in range(1, len(table)):
            ans.append(Interval(table[i - 1][1], table[i][0]))

        return ans