b966: 第 3 題 線段覆蓋長度

#include <bits/stdc++.h>

using namespace std;

typedef struct Node {

	int a, b;

};

bool cmp(Node p, Node q) {

	if (p.a == q.a) return (q.b> p.b);

	else return(p.a < q.a);

}

Node d[10000];

int main() {

	int n, cnt,s,e;

	while (cin>>n) {

		cnt = 0;

		for (int i = 0; i<n; i++) {

			cin>>d[i].a>>d[i].b;

		}

		sort(d, d + n, cmp);  // 將區間的開始數值由小到大排序， 

		for (int i = 0; i < n;i++) {

			s = d[i].a;

			e = d[i].b;

			while ((i + 1 < n) && d[i + 1].a < e) {  //s 與 e 是否包含下一個區間的開始數值 

				if (d[i + 1].b <= e) i++;  // 包含下一個區間的全部，忽略此區間 

				else {

					e = d[i + 1].b; // 未包含下一個區間的全部，但有重疊，將 e 改成下一個區間的結束值 

					i++;

				}

			}

			cnt = cnt + e - s;  // 此區間的範圍數值個數 

		}

        cout<<cnt<<endl;

	}

}