#C++# 不相交线段，多多指导

Question

题目：
数轴上有 n 条线段，第 i ( 1 ≤ i ≤ n ) 条线段覆盖的范围是 a[ i ] 到 b[ i ]，请问最多可以从中选出几条线段，使得任意两条选出的线段都没有重叠部分（有一个公共点也算重叠，比如说一条线段从 1 覆盖到 2，另一条线段从 2 覆盖到 3，这两条线段也算有重叠部分）？

---

输入格式：
第一行一个整数 n。接下来 n 行，每行两个整数 ai,bi 描述一条线段。输出格式输出一行一个整数，表示最多可以选出几条线段。

---

样例输入：
3
1 4
3 6
5 7
样例输出：
2

---

数据规模：
对于 100% 的数据，保证 1 ≤ n ≤ 100000，−10^9 ≤ a[ i ] ≤ b[ i ] ≤ 10^9。

---

#include <bits/stdc++.h>
using namespace std;

int cmp(int a, int b) {
    return a < b;
}

int main() {
    int n;
    scanf("%d", &n);

    int left[n], right[n];
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &left[i], &right[i]);
    }

    sort(right, right + n, cmp);

    int count = 1;
    int last_right = right[0];

    for (int i = 1; i < n; i++)
        if (left[i] > last_right) {
            count++;
            last_right = right[i];
        }

    printf("%d\n", count);

    return 0;
}

不知道为什么做不对，请专家指导

Answer 1

引用 皆我百晓生 小程序内容作答：

你的代码看起来基本上是正确的。不过有一个问题是你的比较函数cmp应该返回a是否小于等于b，而不仅仅是小于。修改一下这个比较函数：

int cmp(int a, int b) {
    return a <= b;
}

接下来，你可以使用一个贪心算法来解决这个问题。先将右端点按照升序排序，然后遍历线段，如果当前线段的左端点大于前一个选中线段的右端点，那么就可以选择这条线段。具体代码如下：

#include <bits/stdc++.h>
using namespace std;
 
bool cmp(pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
}
 
int main() {
    int n;
    cin >> n;
 
    vector<pair<int, int>> segments(n);
    for (int i = 0; i < n; i++) {
        cin >> segments[i].first >> segments[i].second;
    }
 
    sort(segments.begin(), segments.end(), cmp);
 
    int count = 1;
    int last_right = segments[0].second;
 
    for (int i = 1; i < n; i++) {
        if (segments[i].first > last_right) {
            count++;
            last_right = segments[i].second;
        }
    }
 
    cout << count << endl;
 
    return 0;
}

这样就可以正确地计算出最多可以选出几条线段。希望对你有帮助！