题目

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:

  1. Input: [ [1,2] ]
  3. Output: [-1]
  5. Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

  1. Input: [ [3,4], [2,3], [1,2] ]
  3. Output: [-1, 0, 1]
  5. Explanation: There is no satisfied "right" interval for [3,4].
  6. For [2,3], the interval [3,4] has minimum-"right" start point;
  7. For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

  1. Input: [ [1,4], [2,3], [3,4] ]
  3. Output: [-1, 2, -1]
  5. Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
  6. For [2,3], the interval [3,4] has minimum-"right" start point.

题意

给定一个区间集合S，对于其中的每一个区间s，判断能否在S中找到一个区间t，使得t的左端点大于等于s的右端点。如果能，则找到左端点最小的t。

思路

相当于给定两组数，一组为左端点的集合L，另一组为右端点的集合R，对于R中任意一个点a，在L中找到大于等于a的最小点b。使用二分法查找。

代码实现

Java

  1. class Solution {
  2.     public int[] findRightInterval(int[][] intervals) {
  3.         int[] ans = new int[intervals.length];
  5.           // 将左端点抽出来和下标绑定，并排序
  6.         List<int[]> indices = new ArrayList<>();
  7.         for (int i = 0; i < intervals.length; i++) {
  8.             indices.add(new int[] { intervals[i][0], i });
  9.         }
  10.         Collections.sort(indices, (int[] a, int[] b) -> a[0] - b[0]);
  12.         for (int i = 0; i < intervals.length; i++) {
  13.             int left = 0, right = indices.size() - 1;
  14.             int target = intervals[i][1];
  15.             while (left < right) {
  16.                 int mid = (right - left) / 2 + left;
  17.                 if (indices.get(mid)[0] < target) {
  18.                     left = mid + 1;
  19.                 } else {
  20.                     right = mid;
  21.                 }
  22.             }
  23.             if (indices.get(left)[0] >= target) {
  24.                 ans[i] = indices.get(left)[1];
  25.             } else {
  26.                 ans[i] = -1;
  27.             }
  28.         }
  30.         return ans;
  31.     }
  32. }

JavaScript

  1. /**
  2.  * @param {number[][]} intervals
  3.  * @return {number[]}
  4.  */
  5. var findRightInterval = function (intervals) {
  6.   let ans = []
  7.   let lefts = []
  8.   intervals.forEach((interval, index) => lefts.push([interval[0], index]))
  9.   lefts.sort((a, b) => a[0] - b[0])
  10.   intervals.forEach(interval => {
  11.     let left = 0, right = lefts.length - 1
  12.     while (left < right) {
  13.       let mid = Math.trunc((right - left) / 2) + left
  14.       if (interval[1] > lefts[mid][0]) {
  15.         left = mid + 1
  16.       } else {
  17.         right = mid
  18.       }
  19.     }
  20.     ans.push(lefts[left][0] >= interval[1] ? lefts[left][1] : -1)
  21.   })
  22.   return ans
  23. }