LeetCode 436: Find Right Interval

link

For an interval $( \text{start}_i, \text{end}_i )$ we want to find the lowest $\text{start}_j$ such that $\text{end}_i \le \text{start}_j$ .

Sort and search

Keeping the start times sorted let us find $\text{start}_j$ efficiently with binary-search.

Time: $\mathcal{O}(n \cdot \lg{n})$ , space: $\mathcal{O}(n)$ .

class Solution:
    def find_insert_index(self, end, sorted_starts):
        lo, hi = 0, len(sorted_starts) - 1
        while lo <= hi:
            mid = (lo + hi) // 2
            mid_start, _ = sorted_starts[mid]
            if mid_start < end:
                lo = mid + 1
            else:
                hi = mid - 1

        return sorted_starts[lo][1] if lo < len(sorted_starts) else -1

    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        sorted_starts = sorted(
            [(interval[0], i) for i, interval in enumerate(intervals)]
        )
        right_indices = []
        for start, end in intervals:
            right_indices.append(self.find_insert_index(end, sorted_starts))

        return right_indices

Heaps

Say, in the sorted start-times, we are searching right indices in order of end-times (smaller to bigger). If $\text{start}_j$ does not work for $\text{end}_i$ , that start-time will not work for other end-times and we can get rid of $\text{start}_j$ from all future searches.

To do that, we keep two min heaps: (1) contains start-times (2) contains end-times.

Time: $\mathcal{O}(n \cdot \lg{n})$ , space: $\mathcal{O}(n)$ .

from heapq import heapify, heappop as pop

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        start_q = [(interval[0], i) for i, interval in enumerate(intervals)]
        heapify(start_q)

        end_q = [(interval[1], i) for i, interval in enumerate(intervals)]
        heapify(end_q)

        right_indices = [-1] * len(intervals)
        while end_q:
            while start_q and end_q[0][0] > start_q[0][0]:
                pop(start_q)
            if start_q:
                right_indices[end_q[0][1]] = start_q[0][1]
            pop(end_q)

        return right_indices

unreasonably effective