leetcode-solution/Python/0436-find-right-interval.py at main · hogan-tech/leetcode-solution · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# time complexity: O(nlogn)
# space complexity: O(n)
from heapq import heappop, heappush
from typing import List


class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        startHeap = []
        endHeap = []
        result = [-1] * len(intervals)

        for i, (startTime, endTime) in enumerate(intervals):
            heappush(startHeap, (startTime, i))
            heappush(endHeap, (endTime, i))

        while endHeap:
            currEnd, currEndIdx = heappop(endHeap)
            while startHeap and startHeap[0][0] < currEnd:
                heappop(startHeap)

            if startHeap:
                result[currEndIdx] = startHeap[0][1]

        return result


intervals = [[1, 2]]
print(Solution().findRightInterval(intervals))
intervals = [[3, 4], [2, 3], [1, 2]]
print(Solution().findRightInterval(intervals))
intervals = [[1, 4], [2, 3], [3, 4]]
print(Solution().findRightInterval(intervals))