题解 | 剩下的树 + 区间合并

/* 
          使用了合并区间（力扣-56）的思想：
		  思想：
		  	   先对区间按照左边界进行排序，遍历所有区间，考虑：
			   （1）不重叠，直接加入res，
			   （2）有重叠，修改vector容器res中最后一个元素的右边界值 = max(当前遍历区间右边界,原右边界）
	   	  要点：
	   		1、【改进】第23行代码：判断边界为(L-1)。。。如：(1,3)(4,6)合并为(1,6)，
			2、【学习】auto获取值时需引用，即引用后(*it)返回的是vector<int>，便可通过下标形式访问内部元素。					   （第46行代码）
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<vector<int>> merged(vector<vector<int>>& inputs) {
    if (inputs.size() == 0) {
        return {};
    }
    vector<vector<int>> res;
    for (int i = 0; i<inputs.size(); i++) {
        int L = inputs[i][0], R = inputs[i][1];
        if (res.size()==0 || res.back()[1] < L-1) {
            res.push_back({L, R});
        }
        else {
            res.back()[1] = max(res.back()[1],R);  // 注意取较大值。
        }
    }
    return res;
}

int main() {
    int len, n;
    while (cin >> len >> n) { // 注意 while 处理多个 case
        vector<vector<int>> inputs(n);
        for (int i = 0; i<n; i++) {
            int l,r;
            cin >> l >> r;
            inputs[i]={l,r};
        }
        sort(inputs.begin(), inputs.end());
        vector<vector<int>> res = merged(inputs);
        int cnt = len+1;
        for (auto it = res.begin(); it!=res.end(); it++) {
            cnt -= ((*it)[1]-(*it)[0]+1);
        }
        cout << cnt << endl;
    }
}
// 64 位输出请用 printf("%lld")