蓝桥杯备赛-贪心-区间合并

题目描述

已知有 N 个区间，每个区间的范围是 [si​,ti​]，请求出区间覆盖后的总长。

输入格式

第一行一个正整数 N，表示区间个数。 接下来 N 行，每行两个正整数，表示 si​ 和 ti​。

输出格式

共一行，一个正整数，为覆盖后的区间总长。

输入输出样例

输入 3 1 100000 200001 1000000 100000000 100000001 输出 900002

说明/提示

对于 40% 的数据，N≤1000，1≤si​ #include #include 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; vectora(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; }