You are given an array of intervals, where intervals[i] = [starti, endi] and each starti is unique.
The right interval for an interval i is an interval j such that startj >= endi and startj is minimized.
Return an array of right interval indices for each interval i. If no right interval exists for interval i, then put -1 at index i.
Example 1:
Input: intervals = [[1,2]] Output: [-1] Explanation: There is only one interval in the collection, so it outputs -1.
Example 2:
Input: intervals = [[3,4],[2,3],[1,2]] Output: [-1,0,1] Explanation: There is no right interval for [3,4]. The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3. The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.
Example 3:
Input: intervals = [[1,4],[2,3],[3,4]] Output: [-1,2,-1] Explanation: There is no right interval for [1,4] and [3,4]. The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.
Constraints:
1 <= intervals.length <= 2 * 104intervals[i].length == 2-106 <= starti <= endi <= 106- The start point of each interval is unique.
題目大意： 給定一個區間陣列intervals[i] = [starti, endi]，并且規定陣列里的各區間起點starti是唯一的，對右區間right interval的定義是：對于一個區間intervals[i]，它的右區間intervals[j]是陣列里所有滿足startj>=endi的區間里startj最小的那個區間，現在要求回傳每個區間的右區間對應的陣列索引，如果不存在則回傳-1，
解題思路：要找right interval最簡單的方法就是遍歷整個陣列，一遇到startj>=endi的區間就比較更新，最后得到具有最小startj的那個區間，但是如果陣列是按starti排好序的，那就只要找到第一個（最左邊的）滿足startj>=endi的區間即可，這其實也就是有序陣列的下屆lower bound的概念，因此可以先把陣列按starti排好序然后用二分查找法查找endi的下屆lower bound，
注：題目要求回傳陣列下標，但排序后區間的索引就變了，因此要在排序前用一個map來記錄區間對應原陣列的索引，
class Solution:
def findRightInterval(self, intervals: List[List[int]]) -> List[int]:
n = len(intervals)
indexMap = {}
for i in range(n):
indexMap[tuple(intervals[i])] = i
intervals.sort()
def lowerBound(target):
l, r = 0, n - 1
while l <= r:
mid = (l + r) // 2
if target <= intervals[mid][0]:
r = mid - 1
else:
l = mid + 1
return l
res = [-1] * n
for interval in intervals:
lb = lowerBound(interval[1])
if lb < n:
res[indexMap[tuple(interval)]] = indexMap[tuple(intervals[lb])]
return res轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/396595.html
標籤：其他