數軸上有?n?條線段，選取其中?k?條線段使得這?k𝑘?條線段兩兩沒有重合部分，問?k?最大為多少。

輸入格式

第一行為一個正整數?n；

在接下來的?n?行中，每行有?2?個數?ai,bi，描述每條線段的左右端點坐標。

輸出格式

輸出一個整數，為?k?的最大值。

數據范圍

1≤n≤10^6
0≤ai<bi≤10^6

輸入樣例：

3
0 2
2 4
1 3

輸出樣例：

2

這個問題是一個貪心的問題，我們只需要判斷當前線段的左端點是否小于上一條線段的右端點，然后不斷的更新，最后得到ans

代碼：

#include <bits/stdc++.h>
using namespace std;const int N = 1e6 + 5;struct T {int x;int y;
} a[N];int n, ans = 1;bool cmp(T u, T v) {return u.y < v.y;
}int main() {scanf("%d", &n);for(int i = 0; i < n; i++) {scanf("%d %d", &a[i].x, &a[i].y);}if(n == 1) {printf("1\n");return 0;}sort(a + 0, a + n, cmp);int ed = a[0].y;for(int i = 1; i < n; i++) {if(ed <= a[i].x) {ans++;ed = a[i].y;}}printf("%d\n", ans);return 0;
}

加油?