# 436 - Find Right Interval
解法一 - Two Heaps
一開始的直覺會想到要用 sort + linear search,不過這樣做的時間複雜度是 O(n^2),所以如果可以用 Two Heaps 就能加速。
這個做法的時間複雜度是 O(n*logn),code 如下:
class Solution {
public:
vector<int> findRightInterval(vector<vector<int>>& intervals) {
int n = intervals.size();
if(n == 0) {
return {};
}
// heap for finding the maximum start
priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, startCompare> maxStartHeap;
// heap for finding the minimum end
priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, endCompare> maxEndHeap;
vector<int> result(n, -1);
for (int i = 0; i < n; ++i) {
maxStartHeap.push(make_pair(make_pair(intervals[i][0], intervals[i][1]), i));
maxEndHeap.push(make_pair(make_pair(intervals[i][0], intervals[i][1]), i));
}
// go through all the intervals to find each interval's next interval
for (int i = 0; i < n; i++) {
// let's find the next interval of the interval which has the highest 'end'
auto topEnd = maxEndHeap.top();
maxEndHeap.pop();
if (maxStartHeap.top().first.first >= topEnd.first.second) {
auto topStart = maxStartHeap.top();
maxStartHeap.pop();
// find the the interval that has the closest 'start'
while (!maxStartHeap.empty() && maxStartHeap.top().first.first >= topEnd.first.second) {
topStart = maxStartHeap.top();
maxStartHeap.pop();
}
result[topEnd.second] = topStart.second;
// put the interval back as it could be the next interval of other intervals
maxStartHeap.push(topStart);
}
}
return result;
}
private:
struct startCompare {
bool operator() (const pair<pair<int, int>, int> &x, const pair<pair<int, int>, int> &y) {
return y.first.first > x.first.first;
}
};
struct endCompare {
bool operator()(const pair<pair<int, int>, int> &x, const pair<pair<int, int>, int> &y) {
return y.first.second > x.first.second;
}
};
};
Last updated