题解 | 剩下的树

可应用区间合并的模板

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

int n, m;
vector<PII> lvls;
vector<PII> res;

int main() {
	cin >> n >> m;

	while (m--) {
		int l, r;
		cin >> l >> r;
		lvls.push_back({ l, r });
	}

	// 对起始端点排序
	sort(lvls.begin(), lvls.end());  

	// 合并区间
	int st = -1, ed = -1;                   // 初始区间长度为0(不计入)
	for (auto lvl : lvls) {
		if (ed < lvl.first) {
			if (st != -1)                   // 不输出初始区间
				res.push_back({ st, ed });  // 上一个区间可输出
			st = lvl.first;
			ed = lvl.second;                // 选择当前区间
		}
		else {
			if (lvl.second > ed)            // 合并两区间(延长区间末尾)
				ed = lvl.second;
		}
	}

	// 要计入最后一个区间
	res.push_back({ st, ed });

	int cnt = n + 1;
	for (auto lvl : res) {
		cnt -= (lvl.second - lvl.first + 1);
	}

	cout << cnt << endl;
	return 0; 
}