线段覆盖问题：贪心算法求解及C++代码实现

问题描述：

给定 x 轴上的 N 条线段，如何去掉尽量少的线段，使得剩下的线段两两之间没有重叠部分？

贪心算法思路：

将所有线段按照左端点从小到大排序。2. 选择左端点最小的线段，并标记其右端点。3. 从剩余线段中选择左端点大于已标记右端点的线段，并更新标记右端点。4. 重复步骤3，直到遍历完所有线段。

**C++代码实现：**cpp#include #include using namespace std;

struct Line { int a, b; };

int main() { int N; cin >> N; Line lines[N]; for (int i = 0; i < N; i++) cin >> lines[i].a >> lines[i].b; sort(lines, lines + N, [](Line l1, Line l2) { return l1.a < l2.a; }); int count = 1, last = lines[0].b; for (int i = 1; i < N; i++) { if (lines[i].a > last) { count++; last = lines[i].b; } else { last = min(last, lines[i].b); } } cout << count << endl; return 0;}

代码解释：

使用 struct Line 定义线段结构体，存储线段的左右端点。2. 使用 sort 函数对线段按照左端点升序排序。3. count 变量记录剩余线段数，初始化为1。4. last 变量记录当前已覆盖到的最右端点，初始化为第一个线段的右端点。5. 遍历排序后的线段，如果当前线段的左端点大于 last，说明该线段与之前的线段不重叠，更新 count 和 last。6. 最后输出 count 即为最多剩余线段数。

总结：

本文使用贪心算法解决了线段覆盖问题，并提供了简洁易懂的C++代码实现。该算法时间复杂度为 O(nlogn)，主要由排序决定，是一种高效的解决方法。