题目:
数轴上有 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;
}
不知道为什么做不对,请专家指导