难度: 中等 | 标签: 二分查找

1. 题目描述

https://leetcode.cn/problems/find-right-interval/
题目翻译的很绕, 就是列出每个区间在列表中大于等于右端点的, 另一个最小左端点的区间的索引

给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。
区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。
返回一个由每个区间 i 的 右侧区间 的最小起始位置组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。

示例 1：
输入：intervals = [[1,2]]
输出：[-1]
解释：集合中只有一个区间，所以输出-1。
示例 2：
输入：intervals = [[3,4],[2,3],[1,2]]
输出：[-1,0,1]
解释：对于 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间[3,4]具有最小的“右”起点;
对于 [1,2] ，区间[2,3]具有最小的“右”起点。
示例 3：
输入：intervals = [[1,4],[2,3],[3,4]]
输出：[-1,2,-1]
解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
对于 [2,3] ，区间 [3,4] 有最小的“右”起点。

提示：

  • 1 <= intervals.length <= 2 * 104
  • intervals[i].length == 2
  • -106 <= starti <= endi <= 106
  • 每个间隔的起点都 不相同

通过次数: 21,620 | 提交次数: 39,691

2. 题解

2022-05-20 AC, 被二分坑了下, 返回值也坑了下, 思路倒是很快就想出来了

  1. <?php
  2. /**
  3.  * Created by PhpStorm
  4.  * User: jtahstu
  5.  * Time: 2022/5/20 9:47
  6.  * Des: 436. 寻找右区间
  7.  *      https://leetcode.cn/problems/find-right-interval/
  8.  */
  10. class Solution
  11. {
  13.     /**
  14.      * @param Integer[][] $intervals
  15.      * @return Integer[]
  16.      */
  17.     function findRightInterval($intervals)
  18.     {
  19.         $left_ps = array_column($intervals, 0);
  20.         //先记录下左端点值对应的下标
  21.         $index_ps = array_flip($left_ps);
  22.         sort($left_ps);
  23.         $res = [];
  24.         foreach ($intervals as $interval) {
  25.             //找到数组中>=$interval[1]的最小值
  26.             $k = $this->binarySearch($left_ps, $interval[1]);
  27. //            echo "$interval[1] -> $k\n";
  28.             $res[] = $k == PHP_INT_MIN ? -1 : $index_ps[$k];
  29.         }
  30.         return $res;
  31.     }
  33.     function binarySearch(&$nums, $target)
  34.     {
  35.         $l = 0;
  36.         $r = count($nums) - 1;
  37.         if ($target < $nums[0] || $target > $nums[$r]) return PHP_INT_MIN;
  38.         while ($l < $r) {
  39.             $mid = $l + (($r - $l) >> 1);
  40.             if ($nums[$mid] == $target) {
  41.                 return $target;
  42.             } elseif ($nums[$mid] > $target) {
  43.                 $r = $mid - 1;
  44.             } else {
  45.                 $l = $mid + 1;
  46.             }
  47.         }
  48.         return $nums[$r] < $target ? $nums[$r + 1] : $nums[$r];
  49.     }
  50. }
  53. //print_r((new Solution)->findRightInterval([[1,2]]));
  54. //print_r((new Solution)->findRightInterval([[3, 4], [2, 3], [1, 2], [5, 6]]));
  55. //print_r((new Solution)->findRightInterval([[1, 4], [2, 3], [3, 4]]));
  56. //print_r((new Solution)->findRightInterval([[1, 12], [2, 9], [3, 10], [13, 14], [15, 16], [16, 17]]));  //[3,3,3,4,5,-1]
  57. echo json_encode((new Solution)->findRightInterval([[-10, -8], [-9, -7], [-8, -6], [-7, -5], [-6, -4], [-5, -3], [-4, -2], [-3, -1], [-2, 0], [-1, 1], [0, 2], [1, 3], [2, 4], [3, 5], [4, 6], [5, 7], [6, 8], [7, 9], [8, 10], [9, 11], [10, 12]]));
  59. /**
  60.  * 执行用时：100 ms, 在所有 PHP 提交中击败了100.00%的用户
  61.  * 内存消耗：32.2 MB, 在所有 PHP 提交中击败了100.00%的用户
  62.  * 通过测试用例：19 / 19
  63.  */