<p>You are given an array of <code>intervals</code>, where <code>intervals[i] = [start<sub>i</sub>, end<sub>i</sub>]</code> and each <code>start<sub>i</sub></code> is <strong>unique</strong>.</p>

<p>The <strong>right interval</strong> for an interval <code>i</code> is an interval <code>j</code> such that <code>start<sub>j</sub> &gt;= end<sub>i</sub></code> and <code>start<sub>j</sub></code> is <strong>minimized</strong>. Note that <code>i</code> may equal <code>j</code>.</p>

<p>Return <em>an array of <strong>right interval</strong> indices for each interval <code>i</code></em>. If no <strong>right interval</strong> exists for interval <code>i</code>, then put <code>-1</code> at index <code>i</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> intervals = [[1,2]]
<strong>Output:</strong> [-1]
<strong>Explanation:</strong> There is only one interval in the collection, so it outputs -1.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> intervals = [[3,4],[2,3],[1,2]]
<strong>Output:</strong> [-1,0,1]
<strong>Explanation:</strong> There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start<sub>0</sub> = 3 is the smallest start that is &gt;= end<sub>1</sub> = 3.
The right interval for [1,2] is [2,3] since start<sub>1</sub> = 2 is the smallest start that is &gt;= end<sub>2</sub> = 2.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> intervals = [[1,4],[2,3],[3,4]]
<strong>Output:</strong> [-1,2,-1]
<strong>Explanation:</strong> There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start<sub>2</sub> = 3 is the smallest start that is &gt;= end<sub>1</sub> = 3.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= intervals.length &lt;= 2 * 10<sup>4</sup></code></li>
	<li><code>intervals[i].length == 2</code></li>
	<li><code>-10<sup>6</sup> &lt;= start<sub>i</sub> &lt;= end<sub>i</sub> &lt;= 10<sup>6</sup></code></li>
	<li>The start point of each interval is <strong>unique</strong>.</li>
</ul>

class Solution:
    def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
        '''
        start is unique
        intervals[i] = [starti, endi], intervals[j] = [startj, endj]
        right:
        1. startj >= endi
        2. startj minimized

        output:
        list of right interval indices

        brute force:
        for i, current in enumerate(intervals):
            current[1]
            for left, right in intervals_left:
                compare right to current[1]
                min_left
        O(n**2) -> O(nlogn)
        '''
        # Map interval's start value to its idx in intervals
        start_to_idx = {}
        for i, (start, end) in enumerate(intervals):
            start_to_idx[start] = i
        
        sorted_starts = sorted(list(start_to_idx.keys()))
        res = []
        for start, end in intervals:
            # If an interval starts where this one ends, we have our answer
            # [1,1] or [1,2][2,4]
            if end in start_to_idx:
                res.append(start_to_idx[end])
            
            # Otherwise search for the insertion point in the sorted starts
            else:
                idx = bisect.bisect_left(sorted_starts, end)
                if idx == len(sorted_starts):
                    res.append(-1)
                else:
                    min_right = sorted_starts[idx]
                    res.append(start_to_idx[min_right])

        return res
22300