# 0436. Find Right Interval

https://leetcode.com/problems/find-right-interval

## Description

You are given an array of `intervals`, where `intervals[i] = [starti, endi]` and each `starti` is **unique**.

The **rightinterval** for an interval `i` is an interval `j` such that `startj``>= endi` and `startj` is **minimized**.

Return _an array of **right interval** indices for each interval `i`_. If no **right interval** exists for interval `i`, then put `-1` at index `i`.

**Example 1:**

```
**Input:** intervals = [[1,2]]
**Output:** [-1]
**Explanation:** There is only one interval in the collection, so it outputs -1.
```

**Example 2:**

```
**Input:** intervals = [[3,4],[2,3],[1,2]]
**Output:** [-1,0,1]
**Explanation:** There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.
```

**Example 3:**

```
**Input:** intervals = [[1,4],[2,3],[3,4]]
**Output:** [-1,2,-1]
**Explanation:** There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.
```

**Constraints:**

* `1 <= intervals.length <= 2 * 104`
* `intervals[i].length == 2`
* `-106 <= starti <= endi <= 106`
* The start point of each interval is **unique**.

## ac

```java
class Solution {
    public int[] findRightInterval(Interval[] intervals) {
        // edge cases
        if (intervals == null || intervals.length == 0) return new int[0];
        
        int n = intervals.length;
        TreeMap<Integer, Integer> tmap = new TreeMap<>();
        for (int i = 0; i < n ; i++) {
            if (!tmap.containsKey(intervals[i].start)) {
                tmap.put(intervals[i].start, i);
            }
        }
        
        int[] res = new int[n];
        for (int i = 0; i < n; i++) {
            Integer ceil = tmap.ceilingKey(intervals[i].end);
            if (ceil == null) {
                res[i] = -1;
            } else {
                res[i] = tmap.get(ceil);
            }
        }
        
        return res;
    }
}

/*
1) TreeMap record every start val end its first index; 2) iterate, find ceiling of start, get the val
*/
```
