Leetcode 2406. Divide Intervals Into Minimum Number of Groups

문제

You are given a 2D integer array intervals where intervals[i] = [lefti, righti] 
represents the inclusive interval [lefti, righti].

You have to divide the intervals into one or more groups 
such that each interval is in exactly one group, 
and no two intervals that are in the same group intersect each other.

Return the minimum number of groups you need to make.

Two intervals intersect if there is at least one common number between them. 
For example, the intervals [1, 5] and [5, 8] intersect.

• 시작 시간과 끝 시간을 포함하는 스케쥴이 담긴 배열이 주어진다.
• 스케쥴이 겹치지 않게 위 스케쥴을 분리할때, 가장 적게 분리할수 있는 수를 구하라.

예시

[[5,10],[6,8],[1,5],[2,3],[1,10]]

• 그룹 1: [1, 5], [6, 8].
• 그룹 2: [2, 3], [5, 10].
• 그룹 3: [1, 10].
• 겹치지 않게 분리하면 총 3개의 그룹이 나온다, 정답은 3

제한

• $1 <= intervals.length <= 10^5$
• $intervals[i].length == 2$
• $1 <= left_i <= right_i <= 10^6$

풀이

1. 주어진 interval을 정렬한다.
2. 끝나는 시간이 담긴 minheap을 만든다. ( 이후 m )
   • 최대한 빨리 끝나는 그룹을 확인하기 위함!
3. m 힙이 비어있으면 첫 값을 넣는다.
4. m 힙의 제일 작은 값에 따라 결정한다.
   • 만약 작은값이 다음 시작값보다 작거나 같다면?
     • 다음 시작하는 시간은 반드시 겹치기 때문에 새로운 그룹에 넣는다.
     • 즉, m 힙에 끝나는 시간을 추가한다.
   • 만약 작은값이 다음 시작값보다 크다면?
     • 겹치지 않는 스케쥴이기에 원래 값을 빼고 새로 넣는다.
     • 즉 새로 그룹을 만들지 않고 원래 그룹을 업데이트 한다.

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        intervals.sort()

        endingTimes = []

        for start, end in intervals:
            if not endingTimes:
                heappush(endingTimes, end)
            else:
                minimumEnd = heappop(endingTimes)
                # 겹칠 경우 다시 그룹에 추가된다.
                if minimumEnd >= start:
                    heappush(endingTimes, minimumEnd)
                # 겹치지 않을때, 겹쳤을때 모두 end 그룹이 생겨나긴 한다.
                # 겹쳤을때는 새로운 그룹
                # 겹치지 않았을때는 원래 그룹이 업데이트
                heappush(endingTimes, end)

        return len(endingTimes)