题目描述
已知有 N 个区间，每个区间的范围是 [si,ti]，请求出区间覆盖后的总长。
输入格式
第一行一个正整数 N，表示区间个数。
接下来 N 行，每行两个正整数，表示 si 和 ti。
输出格式
共一行，一个正整数，为覆盖后的区间总长。
输入输出样例
输入
3 1 100000 200001 1000000 100000000 100000001
输出
900002
说明/提示
对于 40% 的数据，N≤1000，1≤si<ti≤10000。
对于 100% 的数据 ，N≤105，1≤si<ti≤1017。
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
//区间合并，按开始最早进行排序！！！
//合并重合区间，分区间段计算总和
//若是通过移动合并成一条区间，会影响是否重合的比较，例如a,b,c,ab不相邻，bc重合，移动后，新的end判定和c不重合，那么bc重合部分就被计算了两次
//本题意为，将所有线段都覆盖需要多长，覆盖线段允许断开
struct meet {int a;int b;
};
bool cmp(meet x, meet y) {return x.a < y.a;
}
int main() {int n;cin >> n;vector<meet>a(n + 3);for (int i = 1; i <= n; i++) {cin >> a[i].a >> a[i].b;}sort(a.begin() + 1, a.begin() + 1 + n, cmp);int sum = 0;int start = a[1].a;int end = a[1].b;for (int i = 2; i <= n; i++) {if (a[i].a> end) {//不重合，计算现有区间长度，重新开始新区间sum += end - start + 1;//先计算，再更新！！！end = a[i].b;start = a[i].a;//忘记更新起始了}else {//重合或相邻end = max(end,a[i].b);//把i写成1了}}sum += end - start + 1;//计算最后一段cout <<sum;return 0;
}
