3.線段覆蓋長度

題解

因為線段具有疊加性，所以我們可以把線段進行merge，當一個線段的開頭跟另一個線段的結尾有部分重疊時，我們就把兩線段合併，合併後的線段開頭會是index比較小的兩線段開頭，線段結尾會是index比較大的兩線段尾部

當兩線(大線段與新線段)段並無重疊點，那令新讀入的線段為新的大線段，並且把舊的大線段的長度加進去答案

在成立以上條件前，我們要先對輸入排序，免得無法精確計算重複部分

注意:我們在輸出時要再計算一次舊線段長度，否則會漏掉一段線段

AC Code

python

from sys import stdin
n=int(stdin.readline().strip())
data=sorted([list(map(int,stdin.readline().strip().split())) for _ in range(n)])
temp=data[0]
total=0
for i in data:
    if i[0]<=temp[1]:
        temp[0]=min(temp[0],i[0])
        temp[1]=max(temp[1],i[1])
    else:
        total+=temp[1]-temp[0]
        temp=i
print(total+temp[1]-temp[0])

C++

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<vector<int>> data(n);
    for(int i=0;i<n;i++){
        int x,y;cin>>x>>y;
        data[i].push_back(x);
        data[i].push_back(y);
    }
    sort(data.begin(),data.end());
    vector<int> temp=data[0];
    long long total=0;
    for(int i=0;i<n;i++){
        if(data[i][0]<=temp[1]){
            temp[0]=min(temp[0],data[i][0]);
            temp[1]=max(temp[1],data[i][1]);
        }
        else{
            total+=(temp[1]-temp[0]);
            temp=data[i];
        }
    }
    cout<<total+temp[1]-temp[0]<<endl;
}