Massive Algorithms: LeetCode 436 - Find Right Interval

LeetCode 436 - Find Right Interval

http://bookshadow.com/weblog/2016/10/30/leetcode-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:

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.

https://www.cnblogs.com/liujinhong/p/6399135.html

给定一系列的区间，对于任意一个区间，在所有区间中找到一个区间的起始点大于等于当前区间的结束点，并且要求这两个点最接近。

【思路】

首先对所有区间的起始点进行排序，然后对于每一个区间使用二分查找来找到与这个区间结束点最接近的起始点的区间，并且获得该区间的索引。

X. Use TreeMap to store intervals
Use TreeMap<Integer, PriorityQueue<Integer|Interval>> to handle duplicate start
https://leetcode.com/problems/find-right-interval/discuss/91789/java-clear-on-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]]
the correct answer should be
[-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<>();
           pq.add(i);
           map.put(intervals[i].start, pq);
          }
          else{
           map.get(intervals[i].start).add(i);
          }
         }
         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://leetcode.com/problems/find-right-interval/discuss/91815/Commented-Java-O(n*logn)-solution.-Sort-%2B-Binary-Search.

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;
    }

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:

Sort starts
For each end, find leftmost start using binary search
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);
        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;
        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:

Clone intervals and update end with index.
Sort clone-intervals by start
Iterate over each interval and find the right by binary searching the clone-intervals.
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

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.

Iterate intervals array and fill a points list, then sort it
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++) {
        points.add(new Point(intervals[i].start, 1, i));
        points.add(new Point(intervals[i].end, 0, 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;
            prevIdxs.add(point.index);
        }
    }
    
    return res;
}

http://www.voidcn.com/article/p-qrdsmkvw-bmq.html

public int[] findRightInterval(Interval[] intervals) {  
 int n=intervals.length;
 if(n==1){
  return new int[]{-1};
 }
 int[] result=new int[n];
 IntervalWithIndex[] intervalWithIndexs=new IntervalWithIndex[n];
 for(int i=0;i<n;i++){
  IntervalWithIndex in=new IntervalWithIndex(intervals[i], i);
  intervalWithIndexs[i]=in;
 }
 Arrays.sort(intervalWithIndexs, (a,b)->(a.interval.start-b.interval.start));
 for(int i=0;i<n;i++){
  int index=intervalWithIndexs[i].index;
  Interval interval=intervalWithIndexs[i].interval;
  boolean isFind=false;
  for(int j=i+1;j<n;j++){
   if(intervalWithIndexs[j].interval.start>=interval.end){
    isFind=true;
    result[index]=intervalWithIndexs[j].index;
    break;
   }
  }
  if(isFind==false){
   result[index]=-1;
  }
 }
 return result;
}

class IntervalWithIndex{
 Interval interval;
 int index;
 public IntervalWithIndex(Interval interval,int index) {
  this.interval=interval;
  this.index=index;
 }
}

http://www.cnblogs.com/grandyang/p/6018581.html

Non-overlapping Intervals

Data Stream as Disjoint Intervals

Insert Interval

Merge Intervals

LeetCode 436 - Find Right Interval

Labels

Popular Posts