I'm getting WAs.. but don't know why..
My approach is greedy.. anybody has an idea..?
- Code: Select all
#include <stdio.h>
#include <string.h>
#define min(x, y) ((x) > (y) ? (y) : (x))
#define max(x, y) ((x) > (y) ? (x) : (y))
typedef struct _d {
int left, right;
} DATA;
DATA data[500001];
int n, m;
int comp(const void* x, const void* y)
{
DATA* a = (DATA*)x;
DATA* b = (DATA*)y;
if (a->left != b->left)
return a->left - b->left;
return b->right - a->right;
}
int main()
{
int tc;
int i, j, cnt;
int min1, max1;
scanf("%d", &tc);
while (tc--) {
scanf("%d%d", &n, &m);
for (i = 0; i < m; i++) {
scanf("%d%d", &data[i].left, &data[i].right);
}
qsort(data, m, sizeof(DATA), comp);
i = cnt = 0;
max1 = min1 = 1;
while (1) {
while (i < m) {
if (data[i].left > min1)
break;
max1 = max(max1, data[i].right);
i++;
}
cnt++;
min1 = max1;
if (max1 >= n)
break;
}
printf("%d\n", cnt);
if (tc)
printf("\n");
}
return 0;
}