# 436. Find Right Interval

```
T: O(nlogn)
S: O(n)
```

````java
```java
class Solution {
    public int[] findRightInterval(int[][] intervals) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < intervals.length; i++) {
            map.put(intervals[i][0], i);
        }
        int[] result = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            Integer key = map.ceilingKey(intervals[i][1]); // find >= cur end
            if (key == null) {
                result[i] = -1;
            } else {
                result[i] = map.get(key);
            }
        }
        return result;
    }
}

/***
using treemap
fixed start sort

-> value is index

then use end to find if there is another bigger interval in right side

T: O(nlogn)
S: O(n)

[[1,4],[2,3],[3,4]]


1,    4
   23
    3,4 

1.  


i , j

i end <= startj

using index

          [3,4]
     [2,3]
[1,2]



[0,6] [1,2]
    
 ----------
    ----


    1,      4
      2 , 3
          3,4 

   ----
-----------

-1, 0, 1
 */
```
````
