请你给我写个线段合并的代码模版,用cpp写。
创建于:2025年4月12日
使用 O3 Mini High 回答 Chat01
创建于:2025年4月12日
使用 O3 Mini High 回答 Chat01
请你给我写个线段合并的代码模版,用cpp写。
下面是一份用 C++ 实现线段合并的代码模版,此代码首先读取若干线段,然后按照区间起点排序,接着遍历线段依次进行合并,最后输出合并后的区间。请根据你的实际需要进行调整:
cpp#include <iostream> #include <vector> #include <algorithm> struct Segment { int start, end; }; int main() { int n; std::cout << "请输入线段数量:" << std::endl; std::cin >> n; std::vector<Segment> segments(n); std::cout << "请输入每个线段的起点和终点(用空格分隔):" << std::endl; for (int i = 0; i < n; i++) { std::cin >> segments[i].start >> segments[i].end; } // 根据线段的起点进行排序,若起点相同则按照终点排序 std::sort(segments.begin(), segments.end(), [](const Segment &a, const Segment &b) { return (a.start < b.start) || (a.start == b.start && a.end < b.end); }); std::vector<Segment> merged; if (!segments.empty()) { // 将第一个线段作为初始合并区间 merged.push_back(segments[0]); // 遍历所有线段,进行合并操作 for (int i = 1; i < n; i++) { // 若当前线段的起点在已合并线段的末尾之前或正好相等,则可合并 if (segments[i].start <= merged.back().end) { // 更新当前合并线段的终点为两者终点的最大值 merged.back().end = std::max(merged.back().end, segments[i].end); } else { // 否则,将当前线段加入结果集合 merged.push_back(segments[i]); } } } // 输出合并后的线段 std::cout << "合并后的线段为:" << std::endl; for (const auto &seg : merged) { std::cout << seg.start << " " << seg.end << std::endl; } return 0; }
结构体定义:
定义了一个 Segment
结构体,包含 start
(起点)和 end
(终点)。
输入部分:
用户首先输入线段数量,然后依次输入每个线段的起点和终点。
排序:
使用 std::sort
按起点(若起点相同则按终点)对所有线段进行排序,为后续合并操作做准备。
合并过程:
输出:
遍历 merged
容器,输出每个合并后的线段。
这份代码模版可以作为解决常见线段合并问题的基础模版,根据不同问题要求你可以进一步扩展或修改细节。