leetcode 757

問題

給定一些區間 intervals[i], intervals[i][0] 為左邊界, intervals[i][1] 為右邊界
找出一個整數集合 S, 使得任意一個 intervals[i] 與 S 相交的個數至少為 2

構想

先將 intervals 排序, 由於我們希望在選兩個重疊的點的時候能夠重複利用
所以我們以右邊界來排序, 如果右邊界相等, 那麼左邊界較右邊的排在前面

假設兩個點 left 與 right 與 intervals[i] 相交
在檢查 intervals[i+1] 時

• left 大於等於 intervals[i+1] 的左邊界, 意味著 right 也在 intervals[i+1] 的區間裡
• left 小於 intervals[i+1] 的左邊界, 但是 right 大於等於 intervals[i+1] 的左邊界, 代表左邊界要重選, 並解將 left 放進 S 裡
• left 與 right 都小於 itnervals[i+1] 的左邊界, 代表 left 與 right 都要重選, 並將 left 與 right 放進 S 裡

在重選時, 由於區間已排序過, 選擇區間的右邊界是保險的作法

大专栏  leetcode 757>解法

class Solution {
public:
    int intersectionSizeTwo(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](vector<int> &a, vector<int> &b) {
            if (a[1] < b[1]) {
                return true;
            } else if (a[1] == b[1] && a[0] > b[0]) {
                return true;
            } else {
                return false;
            }
        });
        int n = intervals.size();
        int ret = 0;
        int left = -1, right = -1;
        for (int i=0; i<n; i++) {
            if (intervals[i][0] > left) {
                if (intervals[i][0] > right) {
                    ret += 2;
                    right = intervals[i][1];
                    left = right - 1;
                } else {
                    ret ++;
                    left = right;
                    right = intervals[i][1];
                }
            }
        }
        return ret;
    }
};

分析

40ms 100% beat
time complexity: O(nlogn)