题目描述
区间合并,不是对左侧端点排序就是对右侧端点排序。本题对左侧端点排序。
样例
#define N 100010
int cmp(const void *A, const void *B) {
int *pA = (int *)A;
int *pB = (int *)B;
return pA[0] > pB[0] ? 1 : -1;
}
int main() {
int n, l, r, ans, a[N][2];
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &l, &r);
a[i][0] = l;
a[i][1] = r;
}
qsort(a, n, sizeof(a[0]), cmp);
ans = 1;
l = a[0][0];
r = a[0][1];
for (int i = 1; i < n; i++) {
if (a[i][0] > r) { // 当前区间的左侧端点严格大于维护的r 说明是一个新的区间
ans++;
l = a[i][0];
r = a[i][1];
} else { // 否则, 说明i区间和维护的区间有交集,此时需要刷新区间的最右端点。
r = fmax(r, a[i][1]);
}
}
printf("%d", ans);
return 0;
}