Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.
For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.
Example：
Input: [ [3,4], [2,3], [1,2] ]
Output: [-1, 0, 1]
Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.
Note：
You may assume the interval's end point is always bigger than its start point.
You may assume none of these intervals have the same start point.
解释下题目：
给定一个数组，里面是一个又一个长度为2的数组，对应的是一个又一个闭区间，然后对于其中的每一个闭区间，找到一个在它右边的闭区间，而且这个闭区间离得越近越好。
1. 暴力搜索
实际耗时：418ms
public int[] findRightInterval(int[][] intervals) {
int[] res = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
boolean hasFound = false;
int end = intervals[i][1];
int minStart = Integer.MAX_VALUE;
int minStartIndex = -1;
//System.out.println("end = " + end);
for (int j = 0; j < intervals.length; j++) {
int start = intervals[j][0];
//System.out.println("start = " + start);
if (start >= end) {
hasFound = true;
if (start < minStart) {
minStart = start;
minStartIndex = j;
}
}
}
if (!hasFound) {
res[i] = -1;
} else {
res[i] = minStartIndex;
}
return res;
}
暴力搜索的话就没有什么可说的，对于每一个区间，都需要遍历一遍整个数组去寻找。
时间复杂度O(n^2)
空间复杂度O(1)
2. 利用NavigableMap
实际耗时：14ms
public int[] findRightInterval(int[][] intervals) {
int[] result = new int[intervals.length];
NavigableMap<Integer, Integer> intervalMap = new TreeMap<>
for (int i = 0; i < intervals.length; i++) {
intervalMap.put(intervals[i][0], i);
for (int i = 0; i < intervals.length; i++) {
Map.Entry<Integer, Integer> entry = intervalMap.ceilingEntry(intervals[i][1]);
result[i] = (entry != null) ? entry.getValue() : -1;
return result;
}
这个如果是了解了NavigableMap就很简单，如果不了解就还是比较困难
