线段覆盖 - 贪心算法求解最大不重叠线段数量

问题描述

给定 $x$ 轴上的 $N$（$0 < N < 100$）条线段，每个线段由它的二个端点 $a_i$ 和 $b_i$ 确定，$i = 1, 2, \dots, N$，这些坐标都是区间 $(-999, 999)$ 的整数。有些线段之间会相互交叠或覆盖。请你编写一个程序，从给出的线段中去掉尽量少的线段，使得剩下的线段两两之间没有内部公共点。所谓的内部公共点是指一个点同时属于两条线段且至少在其中一条线段的内部（即除去端点的部分）。

解决方案

我们可以通过贪心的方法来解决这个问题。首先，我们将所有的线段按照起点从小到大排序。然后，我们从第一个线段开始，将其终点作为当前终点。接下来，我们依次遍历每个线段，如果当前线段的起点大于当前终点，说明这个线段与前面的线段没有重叠，我们就可以将前面的线段加入最终的结果中，并更新当前终点为当前线段的终点。如果当前线段的起点小于等于当前终点，说明这个线段与前面的线段有重叠，我们只需要更新当前终点为当前线段终点的最小值即可。最后，我们将最后一个线段加入最终的结果中即可。

C++ 代码

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

using namespace std;

struct Segment {
    int start;
    int end;
};

bool compareSegments(Segment a, Segment b) {
    if (a.start == b.start) {
        return a.end < b.end;
    }
    return a.start < b.start;
}

int main() {
    int N;
    cin >> N;

    vector<Segment> segments(N);

    for (int i = 0; i < N; i++) {
        cin >> segments[i].start >> segments[i].end;
    }

    sort(segments.begin(), segments.end(), compareSegments);

    int count = 1;
    int currentEnd = segments[0].end;

    for (int i = 1; i < N; i++) {
        if (segments[i].start > currentEnd) {
            count++;
            currentEnd = segments[i].end;
        } else {
            currentEnd = min(currentEnd, segments[i].end);
        }
    }

    cout << count << endl;

    return 0;
}

算法复杂度分析

排序部分：$O(N log N)$。
遍历部分：$O(N)$。

因此，算法的时间复杂度为 $O(N log N)$。

代码说明

compareSegments 函数用于比较两个线段，首先比较起点，如果起点相同则比较终点。
main 函数中，首先读取输入数据，然后对线段按照起点从小到大排序。
遍历所有线段，使用贪心策略选择不重叠的线段。
count 变量用于记录选出的线段数量。
currentEnd 变量用于记录当前已选线段的最大的终点。

例子

输入：

输出：

解释：

我们可以选择线段 (1, 3) 和 (6, 3)，它们没有内部公共点。

总结

通过贪心算法，我们可以有效地解决线段覆盖问题，找到最大不重叠线段的数量。