寻找右区间

题目链接

寻找右区间

题目描述

注意点

-10^6 <= starti <= endi <= 10^6
每个间隔的起点都不相同
如果某个区间 i 不存在对应的右侧区间，则下标 i 处的值设为 -1

解答思路

因为本题需要找到每个interval大于interval对应end的最小start值，所以首先想到将start进行排序，又因为输出结果与原区间的顺序相同，所以使用一个新的数组leftIdxArr存储start及其在原数组对应的下标，随后对leftIdxArr进行排序
排序后遍历leftIdxArr，根据leftIdxArr[i][1]可以取得其在intervals的下标idx，也就能取到对应的end（intervals[idx][1]），然后对leftIdxArr二分查找大于end的最小start即可

代码

class Solution {public int[] findRightInterval(int[][] intervals) {int n = intervals.length;int[] res = new int[n];int[][] leftIdxArr = new int[n][2];for (int i = 0; i < n; i++) {leftIdxArr[i][0] = intervals[i][0];leftIdxArr[i][1] = i;}// 左区间从小到大进行排序Arrays.sort(leftIdxArr, new Comparator<int[]>() {public int compare(int[] a, int[] b) {return a[0] - b[0];}});for (int i = 0; i < n; i++) {int idx = leftIdxArr[i][1];int rightVal = intervals[idx][1];if (rightVal > leftIdxArr[n - 1][0]) {res[idx] = -1;continue;}// 二分查找找到最小“右”起点的下标res[idx] = binarySearch(leftIdxArr, rightVal, i, n - 1);}return res;}public int binarySearch(int[][] leftIdxArr, int rightVal, int left, int right) {while (left < right) {int mid = left + ((right - left) >> 1);if (rightVal > leftIdxArr[mid][0]) {left = mid + 1;} else {right = mid;}}return leftIdxArr[left][1];}
}