線段重合

思路

重合的線段部份，開頭一定是這些線段開始位置最靠後的。

1. 將線段排序，隨後遍歷，過程中判斷當前重合的線段共有幾個（簡稱合法線段）。
   • 因為已經排好序，新加入的線段開頭一定比較靠後，也就算做是新的起點。
2. 我們想要從之前的答案當中推出現在的，唯一的不同是重合線段的起點不一樣。
   • 因此，原答案參考的線段當中，「終點要比當前起點靠前」的線段就得去除掉（不合法線段要去除掉）。

以上兩步操作，需要快速去除不合法的線段，並且隨時會有新的合法線段加入。
滿足條件的資料結構就是heap，能在加入新資料時維持有序性，且能依據有序性去除不合法的線段。

程式碼

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
    int n, from, to;
    cin >> n;
    vector<pair<int, int>> nums;
    for(int i = 0; i < n; ++i) {
        cin >> from >> to;
        nums.emplace_back(from, to);
    }
    priority_queue<int, vector<int>, greater<>> minHeap;
    sort(nums.begin(), nums.end());
    int res = 0;
    for(auto& p : nums) {
        // 起點更新, 去除掉不重合的線段
        while(!minHeap.empty() && p.first >= minHeap.top()) {
            minHeap.pop();
        }
        minHeap.push(p.second);
        res = max(res, (int)(minHeap.size()));
    }
    cout << res;
}

複雜度分析

• 時間複雜度：$O(n\log{n})$
• 空間複雜度：$O(n)$