# 資料結構題 - 線段覆蓋長度 - APCS - by Peter Wang
## 題目資訊
此題為2016.3.5測驗中的題目3
###### tags: `APCS`

## 題目敘述

給定一維座標上一些線段，求這些線段所覆蓋的長度，注意，重疊的部分只能算一次。

例如給定 4 個線段：(5, 6)、(1, 2)、(4, 8)、(7, 9)，如下圖，線段覆蓋長度為 6 。


### 輸入：
第一列是一個正整數 N ，表示此測資有 N 個線段。
接著的 N 列每一列是一個線段的開始端點座標整數值 L 和結束端點座標整數值 R ，開始端點座標值小於等於結束端點座標值，兩者之間以一個空格區隔。

### 輸出：
輸出其總覆蓋的長度。

## 解題思路
自己定義一個sort的方式排序。
ans的算法，是只要沒有連續就把目前算到的線段加進去。

## 程式碼

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
#define ll long long

bool cmp(pair<ll,ll> a,pair<ll,ll> b){
  if(a.first==b.first){
    return a.second<b.second;
  }
  return a.first<b.first;
}

int main() {
  int n;
  while(cin>>n){
    pair<ll,ll> l[n];
    for(int i=0;i<n;i++){
      cin>>l[i].first>>l[i].second;
    }
    sort(l,l+n,cmp);
    ll le=l[0].first,r=l[0].second;
    ll ans=0;
    for(int i=1;i<n;i++){
      if(l[i].first<=r){
        if(l[i].second>=r) r=l[i].second;
      }
      else{
        ans+=r-le;
        le=l[i].first;
        r=l[i].second;
      }
    }
    ans+=r-le;
    cout<<ans<<endl;
  }
}

## 資料來源
[zerojudge](https://zerojudge.tw/)
[題目敘述](https://zerojudge.tw/ShowProblem?problemid=b966)

## 備註
>[name=PeterWang]
>[time=Sun, Jun 13, 2021 9:51 AM]