难度: Medium
原题连接
内容描述
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.
思路 1 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
打算先按照start,end排个序，然后只要往后面找就行，虽然是O(N^2),但是稍微小了点，但没想到结果超时。
class Solution(object):
def findRightInterval(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[int]
"""
res = [-1] * len(intervals)
new_intervals = sorted(intervals, key = lambda x: (x.start, x.end))
lookup = {}
for idx, interval in enumerate(intervals):
lookup[(interval.start, interval.end)] = idx
for i in range(len(new_intervals)):
for j in range(i+1, len(new_intervals)):
if new_intervals[j].start >= new_intervals[i].end:
look_interval = (new_intervals[i].start, new_intervals[i].end)
look_idx = lookup[look_interval]
next_interval = (new_intervals[j].start, new_intervals[j].end)
next_idx = lookup[next_interval]
res[look_idx] = next_idx
break
return res
思路 2 - 时间复杂度: O(N^2)- 空间复杂度: O(N)******
后面我想到既然所有的start都不一样，我不如搞一个list存排过序的start，然后这样就可以用二分查找来找到第一个大于某end的idx了， 同样的用一个字典来存start和idx的信息。
这个二分的思想就是找到第一个大于target的index，思路跟leetcode第35题一样
class Solution(object):
def findRightInterval(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[int]
"""
res = [-1] * len(intervals)
starts = sorted([i.start for i in intervals])
lookup = {}
for idx, interval in enumerate(intervals):
lookup[interval.start] = idx
for i in range(len(intervals)):
if starts[-1] < intervals[i].end:
continue
else:
l, r = 0, len(starts) - 1
target = intervals[i].end
# print(i, l, r, target)
while l <= r:
mid = l + ((r-l) >> 1)
if starts[mid] < target:
l = mid + 1
else:
r = mid - 1
res[i] = lookup[starts[l]]
return res就是题目变成
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 start point of the interval i,
which can be called that j is on the "right" of i.
思路 1 - 时间复杂度: O(NlgN)- 空间复杂度: O(N)******
class Solution(object):
def findRightInterval(self, intervals):
"""
:type intervals: List[Interval]
:rtype: List[int]
"""
res = [-1] * len(intervals)
new_intervals = sorted(intervals, key = lambda x: (x.start, x.end))
lookup = {}
for idx, interval in enumerate(intervals):
lookup[(interval.start, interval.end)] = idx
for i in range(len(new_intervals)-1):
look_interval = (new_intervals[i].start, new_intervals[i].end)
look_idx = lookup[look_interval]
next_interval = (new_intervals[i+1].start, new_intervals[i+1].end)
next_idx = lookup[next_interval]
res[look_idx] = next_idx
return res