题解 第二章暴力求解| #剩下的树#

思路如下

创建一个结构体数组,每一个结构体中都存有区间的左右值

在取数组的时候对其进行遍历

使每一个新来的区间结构体,都将之前的所有有交集的区间给吸收

而将被吸收的区间置空

随后遍历一次该结构体数组

即可得待减去的个数

从而易知,剩下多少

#include <bits/stdc++.h>
using namespace std;

typedef struct interval
{
        int leftSide, rightSide;
} interval;

int main()
{
        int L = 0, repeatTimes = 0;
        cin >> L >> repeatTimes;
        interval inter[repeatTimes];
        for (int i = 0; i < repeatTimes; i++)
        {
                cin >> inter[i].leftSide >> inter[i].rightSide;
                for (int j = 0; j < i; j++)
                {
                        if ((inter[i].leftSide <= inter[j].rightSide && inter[i].leftSide >= inter[j].leftSide) ||
                            (inter[i].rightSide <= inter[j].rightSide && inter[i].rightSide >= inter[j].leftSide)||
                           (inter[j].leftSide <= inter[i].rightSide && inter[j].leftSide >= inter[i].leftSide) ||
                            (inter[j].rightSide <= inter[i].rightSide && inter[j].rightSide >= inter[i].leftSide))
                        {
                                inter[i].leftSide = min(inter[i].leftSide, inter[j].leftSide);
                                inter[i].rightSide = max(inter[i].rightSide, inter[j].rightSide);
                                inter[j].leftSide = 0;
                                inter[j].rightSide = -1;
                        }
                }
        }
        int minus = 0;
        for (int i = 0; i < repeatTimes; i++)
        {
                minus += inter[i].rightSide - inter[i].leftSide + 1;
        }
        cout << L + 1 - minus << endl;
        return 0;
}