803.区间合并

原题链接

思路：

• 按照左侧端点从小到达排序
• 选取第一个区间的右侧端点作为“基准”pivot_right
• 每次到达下一个区间的时候，观察左端点是否超过pivot_right，如果超过，则更新计数器cnt += 1。更新pivot_right = max(pivot_right, 下一个区间的右端点）

  代码：

  ```cpp

  include

using namespace std;

const int N = 1e5 + 5;

static bool cmp(const pair a, const pair b) { return a.first < b.first; }

int main() { pair a[N]; int n = 0; scanf(“%d”, &n); for (int i = 0; i < n; i++) { scanf(“%d %d”, &a[i].first, &a[i].second); } sort(a, a + n, cmp);

int pivot_right = a[0].second;
int cnt = 1;
for (int i = 1; i < n; i++) {
    if (a[i].first > pivot_right) {
        cnt += 1;
    }
    pivot_right = max(pivot_right, a[i].second);
}
printf("%d\n", cnt);
return 0;

} ```