#38036: pair解 O(n)


100200 (Yu Xuan)

學校 : 高雄市立高雄高級中學
編號 : 169890
來源 : [101.9.184.94]
最後登入時間 :
2024-05-01 17:29:37
b966. 3. 線段覆蓋長度 -- 2016年3月apcs | From: [58.115.145.189] | 發表日期 : 2023-10-22 23:52

#include <bits/stdc++.h>
using namespace std;
#define R 10000002
int main()
{
    int n;
    scanf("%d", &n);
    pair<int,int> thread[n];
    for (int i = 0; i < n; i++) scanf("%d %d", &thread[i].first, &thread[i].second);
    sort(thread, thread+n);
    int ans = 0;
    int from = thread[0].first, to = thread[0].second;
    for (int i = 1; i < n; i++)
    {
        if (thread[i].first <= to)
        {
            to = max(to, thread[i].second);
        }
        else
        {
            ans += to - from;
            from = thread[i].first;
            to = thread[i].second;
        }
    }
    ans += to - from;
    printf("%d", ans);
}

 
ZeroJudge Forum