## Sunday, October 30, 2016

### LeetCode 436 - Find Right Interval

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:
1. You may assume the interval's end point is always bigger than its start point.
2. 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.```
X. Use TreeMap to store intervals
Use TreeMap<Integer, PriorityQueue<Integer|Interval>> to handle duplicate start
https://discuss.leetcode.com/topic/65817/java-clear-o-n-logn-solution-based-on-treemap
``````    public int[] findRightInterval(Interval[] intervals) {
int[] result = new int[intervals.length];
java.util.NavigableMap<Integer, Integer> intervalMap = new TreeMap<>();

for (int i = 0; i < intervals.length; ++i) {
intervalMap.put(intervals[i].start, i);
}

for (int i = 0; i < intervals.length; ++i) {
Map.Entry<Integer, Integer> entry = intervalMap.ceilingEntry(intervals[i].end);
result[i] = (entry != null) ? entry.getValue() : -1;
}

return result;
}``````
- When there is duplicate start
Given that, you are using a treemap, which derived from Map. if you put the same key with a different value it will replace the original one with the newer one. In such case, if you have case like
[[4,6],[1,2],[4,8]]
[-1,0,-1]
However, the answer you provide will give
[-1,2,1]
Because in the treeMap the [4,8] will store as 4->2 ,which replace the
previously inserted [4,6] stored as 4->0 for the Map property.
Anyway, you guys show me how to use treemap, still be a brilliant solution.
Updated:
Here attached my edited code which can fix this problem while passing all the test case.
``````  public int[] findRightInterval(Interval[] intervals) {
TreeMap<Integer, PriorityQueue<Integer>> map = new TreeMap<>();
int[] res = new int[intervals.length];
for(int i=0;i<intervals.length;i++){
if(map.get(intervals[i].start)==null){
PriorityQueue<Integer> pq=new PriorityQueue<>();
map.put(intervals[i].start, pq);
}
else{
}
}
for(int i=0;i<intervals.length;i++) {
Integer key = map.ceilingKey(intervals[i].end);
res[i] = key!=null ?map.get(key).peek() : -1;
}
return res;
}``````

X. 排序（Sort）+ 二分查找（Binary Search） 按照区间起点排序，然后二分查找即可。
https://discuss.leetcode.com/topic/67399/java-concise-binary-search
http://www.cnblogs.com/javanerd/p/6061042.html
`把这些interval按照start从小到大排序，然后对每一个interval用其end去在排好序的队列里面做二分查找，找到符合要求的一个interval`
```public int[] findRightInterval(Interval[] intervals){
Interval[] sortedIntervals = Arrays.copyOf(intervals,intervals.length);
Arrays.sort(sortedIntervals,(o1, o2) -> o1.start - o2.start);
int[] result = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
Interval current = intervals[i];
int insertIndex = Arrays.binarySearch(sortedIntervals, current, (o1, o2) -> o1.start - o2.end);
if (insertIndex < 0){
insertIndex = -insertIndex - 1;
}
if (insertIndex == intervals.length){
result[i] = -1;
}else {
Interval match = sortedIntervals[insertIndex];
for (int j = 0; j < intervals.length; j++){// bad....
if (i != j && match.start == intervals[j].start && match.end == intervals[j].end){
// System.out.println(",old index:"+j);
result[i] = j;
}
}
}

}
return result;
}```

If we are not allowed to use TreeMap:
1. Sort starts
2. For each end, find leftmost start using binary search
3. To get the original index, we need a map
``````public int[] findRightInterval(Interval[] intervals) {
Map<Integer, Integer> map = new HashMap<>();
List<Integer> starts = new ArrayList<>();
for (int i = 0; i < intervals.length; i++) {
map.put(intervals[i].start, i);
}

Collections.sort(starts);
int[] res = new int[intervals.length];
for (int i = 0; i < intervals.length; i++) {
int end = intervals[i].end;
int start = binarySearch(starts, end);
if (start < end) {
res[i] = -1;
} else {
res[i] = map.get(start);
}
}
return res;
}

public int binarySearch(List<Integer> list, int x) {
int left = 0, right = list.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (list.get(mid) < x) {
left = mid + 1;
} else {
right = mid;
}
}
return list.get(left);
}``````
https://discuss.leetcode.com/topic/65641/commented-java-o-n-logn-solution-sort-binary-search
Time compexity: `n*log(n)`
`n*log(n)` for sorting
`log(n)` for binary search X `n` times is `n*log(n)`
Space complexity: `n`
`n` for auxilliary array
Algorithm:
1. Clone intervals and update `end` with index.
2. Sort clone-intervals by `start`
3. Iterate over each interval and find the `right` by binary searching the clone-intervals.
4. If found, shove the `end` i.e., the original index of the `right` interval from clone-intervals into the output array.
``````public int[] findRightInterval(Interval[] intervals) {

int n;
// boundary case
if (intervals == null || (n = intervals.length) == 0) return new int[]{};

// output
int[] res = new int[intervals.length];
// auxilliary array to store sorted intervals
Interval[] sintervals = new Interval[n];

// sintervals don't have any use of 'end', so let's use it for tracking original index
for (int i = 0; i < n; ++i) {
sintervals[i] = new Interval(intervals[i].start, i);
}

// sort
Arrays.sort(sintervals, (a, b)->a.start-b.start);

int i = 0;
for (; i < n; ++i) {
int key = intervals[i].end;
// binary search in sintervals for key
int l = 0, r = n - 1;
int right = -1;
while (l <= r) {
int m = l + (r - l) / 2;
if (sintervals[m].start == key) {
right = sintervals[m].end; // original index is stored in end
break;
} else if (sintervals[m].start < key) {
l = m + 1;
} else {
r = m - 1;
}
}

// if we haven't found the key, try looking for 'start' that's just greater
if ((right == -1) && (l < n) && (sintervals[l].start > key)) {
right = sintervals[l].end; // original index is stored in end
}

res[i] = right;
}

return res;
}``````
X.
https://discuss.leetcode.com/topic/65585/java-sweep-line-solution-o-nlogn
1. wrapper class: Point
1. value
2. flag: 1 indicates start, 2 indicates end
3. index: original pos in intervals array
4. Comparable: sort by value ascending, end in front of start if they have same value.
1. Iterate intervals array and fill a points list, then sort it
2. Iterate points list, since the sequence will be "order by position, and end will come before start".
1. whenever meet a end point, keep a list(prevIdxs) before next start, save original index of curr interval to the list.
2. whenever meet a start point, this start point is the right interval to the intervals in the list (prevIdxs). Take out each index in it and update to result.
``````class Point implements Comparable<Point>{
int val;
int flag; //1 start, 0 end
int index;
public Point(int val, int flag, int index) {
this.val = val;
this.flag = flag;
this.index = index;
}
public int compareTo(Point o) {
if (this.val == o.val) return this.flag - o.flag; //end in front of start
return this.val - o.val;
}
}
public int[] findRightInterval(Interval[] intervals) {
if (intervals == null || intervals.length == 0) return new int[]{};

int[] res = new int[intervals.length];
Arrays.fill(res, -1);

List<Point> points = new ArrayList<>();
for (int i = 0; i < intervals.length; i++) {
}

Collections.sort(points);

int prevEnd = 0;
List<Integer> prevIdxs = new ArrayList<>();

for (Point point: points) {
if (point.flag == 1) {
for (Integer prevIdx: prevIdxs) {
res[prevIdx] = point.index;
}
prevIdxs = new ArrayList<>();
} else {
prevEnd = point.val;
}
}

return res;
}``````
http://www.cnblogs.com/grandyang/p/6018581.html