如何在C++中按线段是否相交对二维向量元素分组

给定二维向量 vector<vector<double>> vec = { { 1, 0.5 },{ 2, 0.5 },{ 2.25, 0.5 },{ 2.6, 0.3 }, {3.3, 0.5 },{ 3, 0.5 },{ 3.1, 0.5 },{ 4, 0.6 } }，每个子向量的首元素是线段起点，次元素是线段长度（即线段为闭区间 [start, start+length]）。需要根据线段是否相交（区间重叠）对元素的1-based索引分组，预期结果为 {{1},{2,3,4},{5,6,7},{8}}。

这里推荐用**并查集（Union-Find/DSU）**来实现，核心思路是：

• 把每个元素转换成对应的区间
• 遍历所有两两元素对，若两个区间重叠，就把它们的索引合并到同一个集合
• 最后把同一个集合的索引按原始顺序整理成分组

完整代码实现 #

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

// 并查集实现，用于高效管理集合合并与查找
class DSU {
private:
    std::vector<int> parent;
public:
    DSU(int n) {
        parent.resize(n);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 路径压缩，优化查找效率
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int fx = find(x);
        int fy = find(y);
        if (fx != fy) {
            parent[fy] = fx; // 将两个集合合并
        }
    }
};

// 核心分组函数
std::vector<std::vector<int>> groupByIntersection(const std::vector<std::vector<double>>& vec) {
    int n = vec.size();
    if (n == 0) return {};

    DSU dsu(n);

    // 遍历所有两两元素对，判断区间是否重叠
    for (int i = 0; i < n; ++i) {
        double start1 = vec[i][0];
        double end1 = start1 + vec[i][1];
        for (int j = i + 1; j < n; ++j) {
            double start2 = vec[j][0];
            double end2 = start2 + vec[j][1];
            // 区间重叠判断：只要不是完全分离，就算重叠
            if (!(end1 <= start2 || end2 <= start1)) {
                dsu.unite(i, j);
            }
        }
    }

    // 按集合根节点收集1-based索引
    std::unordered_map<int, std::vector<int>> groupsMap;
    for (int i = 0; i < n; ++i) {
        int root = dsu.find(i);
        groupsMap[root].push_back(i + 1); // 转换为预期的1-based索引
    }

    // 将分组转换为vector，并按组内最小索引排序，保证输出顺序和预期一致
    std::vector<std::vector<int>> result;
    for (const auto& pair : groupsMap) {
        result.push_back(pair.second);
    }
    std::sort(result.begin(), result.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
        return a[0] < b[0];
    });

    return result;
}

// 测试代码
int main() {
    std::vector<std::vector<double>> vec = { 
        {1, 0.5}, {2, 0.5}, {2.25, 0.5}, {2.6, 0.3}, 
        {3.3, 0.5}, {3, 0.5}, {3.1, 0.5}, {4, 0.6} 
    };
    
    auto groups = groupByIntersection(vec);

    // 按预期格式输出结果
    std::cout << "{";
    for (size_t i = 0; i < groups.size(); ++i) {
        std::cout << "{";
        for (size_t j = 0; j < groups[i].size(); ++j) {
            std::cout << groups[i][j];
            if (j != groups[i].size() - 1) std::cout << ",";
        }
        std::cout << "}";
        if (i != groups.size() - 1) std::cout << ",";
    }
    std::cout << "}" << std::endl;

    return 0;
}

代码说明 #

1. 并查集优化：路径压缩让集合查找和合并的时间复杂度接近O(1)，即使元素数量较多也能高效运行。
2. 区间重叠逻辑：两个闭区间 [s1,e1] 和 [s2,e2] 重叠的条件是不满足完全分离，即 !(e1 <= s2 || e2 <= s1)，等价于 s1 < e2 && s2 < e1。
3. 索引处理：代码将原始0-based索引转换为1-based，符合预期结果的要求；分组后按组内最小索引排序，保证输出顺序和预期一致。
4. 输出验证：main 函数模拟了预期的集合格式输出，方便直接验证结果。

运行这段代码后，输出结果为：{{1},{2,3,4},{5,6,7},{8}}，完全符合需求。

内容的提问来源于stack exchange，提问作者tem