交集｜暴力枚举算法

第一题 - Intersection

题目跳转：交集。

这道题可以用暴力的方法，也可以稍微动点脑筋。看在数据量小，直接打暴力就行了，没必要花时间去找两个线段之间的关系。

注意到 $0 \le L_1 R_1, L_2, R_2 \le 100$，可以新建一个标记数组：如果某个坐标属于某一条线段，那么就将对应索引的标记增加一。最后再遍历一边标记数组，如果存在一个坐标被标记了两遍，那么就证明该坐标被两条线段同时覆盖住了。

最后注意输出的时候要 $-1$，表示区间的长度。（如果没有任何重合的区间，即 ans == 0 时，特判直接输出 $0$ 就可以了。

代码时间复杂度：$O(N)$。

本题的 AC 代码如下：

#include <iostream>
using namespace std;

int a, b, c, d;
int arr[1005], ans;

int main(){
    cin >> a >> b >> c >> d;
    for (int i=a; i<=b; i++) 
        arr[i]++;
    for (int i=c; i<=d; i++) 
        arr[i]++;
    for (int i=0; i<=100; i++)
        ans += (arr[i] == 2);
    cout << max(0, ans-1) << endl;
	return 0;
}