区间贪心

问题描述

数轴上有n个开区间（ai，bi），尽量选择多个区间，是的这些区间两两之间没有共同点。

输入格式

第一行的数字代表有几个区间，如果为0，则退出
后面n行每一行都是一个开区间，用空格分隔

输出格式

输出最多有几个开区间

样例

输入
4
1 3
2 4
3 5
6 7

输出
3

C++实现

#include <bits/stdc++.h>
using namespace std;

const int maxn = 110;

struct Interval {
    int x, y;
}I[maxn];

bool cmp(Interval a, Interval b) {
    if(a.x != b.x)
        return a.x > b.x;
    else
        return a.y < b.y;
}

int main() {
    
    int n;
    while(scanf("%d", &n), n != 0) {
        for(int i = 0; i < n; i++) {
            scanf("%d%d", &I[i].x, &I[i].y);
        }
        sort(I, I + n, cmp);
        int ans = 1, lastx = I[0].x;
        for(int i = 1; i < n; i++) {
            if(I[i].y <= lastx) {
                ans++;
                lastx = I[i].x;
            }
        }
        printf("%d\n", ans);
    }
    
    return 0;
}