题目

思路

• 贪心算法，希望一个点控制尽量多的区间，那么这个点应该贴着区间的右端点，因为一旦离开右端点了，必然失去一个区间。
• 具体怎么做？
  • 1. 按照右端点大小排序
  • 1. 每次读区间的左端点，如果大于既定的right值，说明需要加一个点。同时更新right为该区间的右端点。

       代码

       ```cpp

       include

       include

using namespace std;

const int N = 1e5;

bool cmp (pair a, pair b) { return a.second < b.second; }

int main() { pair nums[N]; int n = 0; cin >> n; for (int i = 0; i < n; ++i) { cin >> nums[i].first >> nums[i].second; } sort(nums, nums + n, cmp);

int right = nums[0].second;
int cnt = 1;
for (int i = 1; i < n; ++i) {
    if (nums[i].first > right) {
        cnt++;
        right = nums[i].second;
    }
}
cout << cnt << endl;
return 0;

}

```