leetcode.com 1851. Minimum Interval to Include Each Query

문제 링크: https://leetcode.com/problems/minimum-interval-to-include-each-query/description/

파이썬 소스: https://bit.ly/3wDBYny

from typing import List
import heapq

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        length = len(intervals)
        intervals.sort()
        heap = []
        dict = {}
        idx = 0

        for q in sorted(queries):
            while idx < length and intervals[idx][0] <= q:
                left, right = intervals[idx]
                l = right - left + 1
                heapq.heappush(heap, [l, right])
                idx += 1

            while heap and heap[0][1] < q:
                heapq.heappop(heap)

            dict[q] = heap[0][0] if heap else -1

        return [dict[q] for q in queries]

leetcode.com 435. Non-overlapping Intervals

문제 링크: https://leetcode.com/problems/non-overlapping-intervals/description/

파이썬 소스: https://bit.ly/49UJxED

from typing import List

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: x[1])

        count_total = len(intervals)
        count_non_overlapped = 1
        prev = 0

        for idx in range(1, count_total):
            # prev의 end가 idx의 start 보다 작거나 같으면
            # 이 둘은 overlapped 되는 부분이 없다는 의미
            if intervals[prev][1] <= intervals[idx][0]:
                prev = idx
                count_non_overlapped += 1

        return count_total - count_non_overlapped

leetcode.com 56. Merge Intervals

문제 링크: https://leetcode.com/problems/merge-intervals/description/

파이썬 소스: https://bit.ly/4bXKm1i

from typing import List

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key = lambda x: x[0])
        answer = [intervals.pop(0)]

        while len(intervals) > 0:
            a_start, a_end = answer.pop()
            b_start, b_end = intervals.pop(0)
            over_lapped: bool = False

            if (a_start <= b_start and b_end <= a_end)  \
                or (a_start <= b_start <= a_end)    \
                or (a_start <= b_end <= a_end):
                over_lapped = True

            if over_lapped:
                start = min(a_start, b_start)
                end = max(a_end, b_end)
                answer.append([start, end])
            else:
                answer.append([a_start, a_end])
                answer.append([b_start, b_end])

        return answer