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

题目：
数轴上有 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;
}

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

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

你的代码看起来基本上是正确的。不过有一个问题是你的比较函数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;
}

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

【以下回答由 GPT 生成】

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool sort_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;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        segments.push_back(make_pair(a, b));
    }

    sort(segments.begin(), segments.end(), sort_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;
}

修改说明： 1. 移除了#include <bits/stdc++.h>，使用了更明确的头文件。 2. 使用cin替换了scanf，使用cout替换了printf，让输入输出更加简洁易懂。 3. 将数组left和right改为了使用stl中的vector来存储每个线段的起点和终点。 4. 修改了排序函数cmp为sort_cmp并重新实现，保证按照线段的终点从小到大进行排序。 5. 修改了代码中的输入输出方式，使得和题目描述的输入输出格式一致。

【相关推荐】

• 你可以看下这个问题的回答https://ask.csdn.net/questions/7551059