AcWing 907. 区间覆盖 C
原题链接
简单
作者:
LaChimere
,
2021-06-13 16:52:26
,
所有人可见
,
阅读 282
C
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define MAXSIZE 100010
#define max(a,b) ((a)>(b)?(a):(b))
int n, start, end;
struct Interval {
int left, right;
} intervals[MAXSIZE];
int compInterval(const void *p1, const void *p2) {
struct Interval *iv1 = (struct Interval*) p1;
struct Interval *iv2 = (struct Interval*) p2;
if (iv1->left < iv2->left) {
return -1;
} else if (iv1->left > iv2->left) {
return 1;
}
return 0;
}
void init() {
scanf("%d%d%d", &start, &end, &n);
for (int i = 0; i < n; ++i) {
scanf("%d%d", &intervals[i].left, &intervals[i].right);
}
qsort(intervals, n, sizeof(struct Interval), compInterval);
}
int main() {
init();
int cnt = 0, flag = 0;
for (int i = 0; i < n; ++i) {
int j, maxRight = INT_MIN;
for (j = i; j < n && intervals[j].left <= start; ++j) {
maxRight = max(maxRight, intervals[j].right);
}
if (maxRight < start) {
break;
}
++cnt;
if (maxRight >= end) {
flag = 1;
break;
}
start = maxRight;
i = j - 1;
}
printf("%d\n", flag ? cnt : -1);
return 0;
}