[1스4코2파] # 244. LeetCode 1851. Minimum Interval to Include Each Query

[1스4코2파] 1명의 스위프트 개발자와 4명의 코틀린 개발자, 2명의 파이썬 개발자코딩 테스트 서막 : 1스4코1파

Rule :

하루에 1문제씩 풀기.
한 문제당 30분씩은 고민하기.
왜 그렇게 풀었는지 공유하기.
하루라도 놓친다면 벌금은 1,000원
백준 플래티넘, 프로그래머스 4단계, 개발자 탈퇴 시 모임 탈퇴 가능

START :

[3코1파] 2023.01.04~ (244일차)
[4코1파] 2023.01.13~ (236일차)
[1스4코1파] 2023.04.12~ (147일차)
[1스4코2파] 2023.05.03 ~ (125일차)

Today :

2023.09.04 [244일차]
LeetCode 1851. Minimum Interval to Include Each Query
https://leetcode.com/problems/minimum-interval-to-include-each-query/

1851. Minimum Interval to Include Each Query

문제 설명

각 간격을 나타내는 정수 배열이 담긴 리스트가 주어질 때, 각 배열의 [i] = [lefti, righti]는 lefti에서 시작하여 righti(포함)에서 끝나는 간격을 나타낸다. 간격의 크기를 포함하는 정수의 수는 righti - lefti + 1로 정의되는데, queries 라는 정수 배열 쿼리가 제공 될때, queries의 의 각 요소는 lefti <= 쿼리[j] <= righti가 되는 가장 작은 간격 i의 크기일 때, 각 간격을 return 하고 각 간격이 존재하지 않으면 -1을 return 한다.

문제 풀이 방법

interval 문제로, heap을 사용해서 구현해야함..
먼저 주어진 invervals을 left 값에 따라 sort를 해주고,
주어진 queries를 돌면서 left, right를 비교하고 heap에 넣어지고 빼주는 일련의 과정을 해주어야 함..

내 코드

 class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort()
        minHeap = []
        res = {}
        i = 0
        for q in sorted(queries):
            while i < len(intervals) and intervals[i][0] <= q:
                l, r = intervals[i]
                heapq.heappush(minHeap, (r - l + 1, r))
                i += 1

            while minHeap and minHeap[0][1] < q:
                heapq.heappop(minHeap)
            res[q] = minHeap[0][0] if minHeap else -1
        return [res[q] for q in queries]

증빙

여담

갸어렵네 hard는 풀이를 봐도 이해하기 어려움
가방 싸고 다시 봐야겠음