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

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
*/