Find Right Interval
update Aug 10, 2017 17:50
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.
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.
Example 1:
Input: [ [1,2] ]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.Example 2:
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.Example 3:
Input: [ [1,4], [2,3], [3,4] ]
Output: [-1, 2, -1]
Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.Basic Idea:
思路1：binary search 先把每个 interval 和原 index 存入 hashmap，然后 copy intervals数组，对其按照 start 排序。然后对原数组中每个interval 的 end，在 sorted array 中 binary search 找第一个大于等于该end 的 interval，它原来的index就对应是一个解。
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
// binary search
public class Solution {
public int[] findRightInterval(Interval[] intervals) {
// 在map中存储index
Map<Interval, Integer> map = new HashMap<>();
for (int i = 0; i < intervals.length; ++i) {
map.put(intervals[i], i);
}
// 生成排序的intervals
Interval[] sorted = new Interval[intervals.length];
for (int i = 0; i < sorted.length; ++i) {
sorted[i] = intervals[i];
}
Arrays.sort(sorted, (a, b) -> a.start - b.start);
// binary search 找答案
int[] res = new int[intervals.length];
for (int i = 0; i < res.length; ++i) {
int next = binarySearch(sorted, map, intervals[i].end);
res[i] = next;
}
return res;
}
// 在排序好的 arr 中找到第一个 start >= target 的interval，返回其在map中对应的的value （index）
// 如果没找到，则返回 -1
private int binarySearch(Interval[] arr, Map<Interval, Integer> map, int target) {
int p = 0, r = arr.length - 1;
while (p + 1 < r) {
int q = (r - p) / 2 + p;
if (arr[q].start < target) p = q;
else r = q;
}
if (arr[p].start >= target) return map.get(arr[p]);
else if (arr[r].start >= target) return map.get(arr[r]);
else return -1;
}
}思路2：TreeMap 利用treemap自带排序的性质，把每个start及其index存入treemap,然后对每个end在map中找大于等于它的最小的start对应的index。
注意TreeMap的使用。
// Using TreeMap
// treemap 存储所有的start-index对，然后对每个原interval的end，找treemap中最小的大于等于它的start的index
public class Solution {
public int[] findRightInterval(Interval[] intervals) {
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 0; i < intervals.length; ++i) {
map.put(intervals[i].start, i);
}
int[] res = new int[intervals.length];
for (int i = 0; i < intervals.length; ++i) {
Map.Entry<Integer, Integer> entry = map.ceilingEntry(intervals[i].end);
res[i] = entry == null ? -1 : entry.getValue();
}
return res;
}
}update Dec 3, 2017 2:10
Update
前面二分法解法存在的问题
之前写这道题的时候犯了大忌，因为实际上 Interval 这个 class 并没有 implement hashCode 方法，直接将其放入 hashMap 是不理智的。事实上我们没有必要在 hashMap 中存放完整的 interval 以及其 index，我们只需要存放 start 和 index 就够了。
所以，这次实现中采用的方法和之前写的 TreeMap 的方法类似：
在 HashMap 中存放所有的 start--index 对；
将所有的start存入一个list，对其升序排序；
对于每个 interval，在前面的list中二分查找大于等于其 end 的最小start；
在 HashMap 中找到之前得到的 start 所对应的 index，就是对应 interval 的解；
Binary Search Java Code 更新：
class Solution {
public int[] findRightInterval(Interval[] intervals) {
Map<Integer, Integer> map = new HashMap<>(); // start--index 对
List<Integer> starts = new ArrayList<>(); // 存start，一会排序
for (int i = 0; i < intervals.length; ++i) {
map.put(intervals[i].start, i);
starts.add(intervals[i].start);
}
Collections.sort(starts);
// 开始
int[] res = new int[intervals.length];
for (int i = 0; i < intervals.length; ++i) {
int end = intervals[i].end;
Integer rightStart = findRightStart(starts, end);
if (rightStart == null) res[i] = -1;
else res[i] = map.get(rightStart);
}
return res;
}
// 用二分法找大于等于 end 的最小start，返回start，如果不存在则反回 null
private Integer findRightStart(List<Integer> starts, int end) {
int p = 0, r = starts.size() - 1;
while (p + 1 < r) {
int q = p + (r - p) / 2;
if (starts.get(q) >= end) r = q;
else p = q;
}
if (starts.get(p) >= end) return starts.get(p);
else if (starts.get(r) >= end) return starts.get(r);
else return null;
}
}