436 - Find Right Interval

解法一 - Two Heaps

``````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;
}
};
};
``````