OJ9858课程选择

Question

辅导机构周末共有n个课程，每个课程有起始时间 begini 和结束时间 endi(begini<endi)，在同一时间，学生只能参加一个课程，且只有全程参加课程才会有收获。
由于有些课程时间上有冲突，家长们又希望学生学到更多的东西，所以怎么安排才能让学生参加的课程数最多呢？
输入格式：
第一行一个整数 n(n≤1000) ；
接下来的 n 行，每行两个整数，第一个 begini，第二个是 endi(0≤begini<endi≤32767)。
输出格式：
输出最多能参加的课程个数。
样例输入1：
3
0 6
0 4
4 8
样例输出1：
2
一开始我想时间少的先上，但如果 6 8，1 7，7 10就不行了，所以做不出来

Answer 1

应该按照结束时间贪心

#include <stdio.h>
#include <algorithm>
using namespace std;

int n, mx = 0, cur = 0, count = 0;

struct meeting {
    int begin;
    int end;
    int interval;
} m[1005];

bool compare(const meeting& m1, const meeting& m2) {
    return m1.end < m2.end;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &m[i].begin, &m[i].end);
        m[i].interval = m[i].end - m[i].begin;
    }
    sort(m, m + n, compare);
    int tmp = 0, sum = 0;
    for (int i = 0; i < n; i++) {

        if (tmp <= m[i].begin) {
            sum++;
            tmp = m[i].end;
        }
    }
    printf("%d", sum);
    return 0;
}