贪心-区间问题

贪心-区间问题

• 贪心常见问题
• • 计算不重合的线段总长度（20220914天翼云）

贪心常见问题 计算不重合的线段总长度（20220914天翼云）

1. 题目描述
   输入n条线段，线段可以用(x, y)表示，x是起点，y是终点。x，y均是整数且满足0。要求计算这些线段所覆盖的不重合区间的总长度。
2. 输入描述

第一行输入n
第二行到第n+1行输入每条线段起点和终点，以逗号分隔

3. 输出描述

总长度

4. 测试用例

输入：
3
1,3
5,7
2,6
输出：
4

5. 注意事项
   输入中以逗号分隔
6. C++代码

#include 
#include 

using namespace std;
const int N = 1e5 + 10;
int n;
struct range
{
	int l, r;
	bool operator< (const range& R) const {
		return l < R.l;
	}
}range[N];

int main()
{
	ios::sync_with_stdio(false);
	cin >> n;
	char p;
	for (int i = 0; i < n; i++) cin >> range[i].l >> p >> range[i].r;
	sort(range, range + n);

	int st = range[0].l, ed = range[0].r, ans = 0;
	for (int i = 1; i < n; i++) {
		if (range[i].l < ed) {
			// 按左边界排序，下一个左边界一定是最靠左边的
			ans += range[i].l - st > 0 ? range[i].l - st : 0;
			if (range[i].r < ed) st = range[i].r;
			else {
				st = ed;
				ed = range[i].r;
			}
		}
		else {
			ans += ed - st;
			st = range[i].l;
			ed = range[i].r;
		}
	}
	ans += ed - st;
	cout << ans;
	return 0;
}