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