简单算法：判断两个集合是否有交集

一、引言

在某些场合我们可能需要判断两个集合是否存在交集，譬如笔者再做的项目，在用户设置的寄存器地址列表中，需要判断寄存器地址设置是否有冲突（寄存器的设置往往通过指定开始地址，以及长度来确定），抽象出来其实就是判断集合交集的问题了。

二、思路

要判断两个数据范围是否存在交集，您可以使用简单的数学比较。对于两个区间 [a, b) 和 [c, d)，它们存在交集的条件是：
$\max(a, c) < min(b, d)$

这个条件确保了两个区间在某个点上重叠。具体来说，这意味着第一个区间的开始点小于第二个区间的结束点，并且第二个区间的开始点小于第一个区间的结束点。

示例解释

譬如对于给出的两个区间 [12, 16) 和 [14, 22) （即我们有一个起始地址12，寄存器长度4；另一个寄存器起始地址14，长度8）：

$\ a = 12, b = 16 \$
$\ c = 14, d = 22 \$

我们可以计算：

$\ max(a, c) = max(12, 14) = 14 \$
$\min(b, d) = min(16, 22) = 16 \$

因为 $\max(a, c) < \min(b, d) \$ （即 ( 14 < 16 )），所以这两个区间存在交集。

代码实现

编写一个简单的 C++ 函数示例：

#include <iostream>
#include <algorithm> // For std::max and std::min

bool hasIntersection(int a, int b, int c, int d) {
    return std::max(a, c) < std::min(b, d);
}

int main() {
    int a = 12, b = 16;
    int c = 14, d = 22;

    if (hasIntersection(a, b, c, d)) {
        std::cout << "The intervals [" << a << ", " << b << ") and [" << c << ", " << d << ") have an intersection." << std::endl;
    } else {
        std::cout << "The intervals do not intersect." << std::endl;
    }

    return 0;
}