leetCode-436:Find Right Interval

问题描述

给定一个二维数组，表示区间的集合。定义区间右侧区间为：区间 i 的右侧区间可以记作区间 j ，并满足 startj`` >= endi ，且 startj 最小化 。注意 i 可能等于 j 。 题目链接：点我

样例输入输出

输入：intervals = [[3,4],[2,3],[1,2]]

输出：[-1,0,1]

解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。

输入：intervals = [[1,4],[2,3],[3,4]]

输出：[-1,2,-1]

解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间 [3,4] 有最小的“右”起点。

问题解法

使用 TreeMap 保存区间左值和区间下标，然后遍历区间，每次取区间右值从 TreeMap 中取出大于等于区间右值的最小 entry，此时其 value 就是当前区间的右区间。代码如下

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++) {
            Map.Entry<Integer, Integer> entry = map.ceilingEntry(intervals[i][1]);
            if (entry == null) {
                result[i] = -1;
            } else {
                result[i] = entry.getValue();
            }
        }
        
        return result;
    }
}