【正经题解】演讲大厅安排

将演讲按照结束时间升序排序，这样可以确保在每个时刻选择结束时间最早的演讲。
初始化动态规划数组 $dp$ ，其中 $dp$ [ $i$ ] 表示在时刻 $i$ 的最大使用时间。
从最后一个演讲开始，向前遍历每个演讲。对于每个演讲，从当前演讲的结束时间向前更新动态规划数组 $dp$ 。
最终， $dp$ [ $p$ ] 即为大厅最大可能的使用时间，其中 $p$ 为排序后的演讲中最晚结束的演讲的结束时间。

#include<iostream>
#include<algorithm>
using namespace std;

struct Time {
    int begin, end;
};

// 自定义比较函数
bool cmp(Time a1, Time a2) {
    if (a1.end != a2.end) {
        return a1.end < a2.end;
    }
    return a1.begin < a2.begin;
}

// 读取输入
int read() {
    int x = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return x * w;
}

int main() {
    int n, p;
    n = read();
    Time a[10005];

    // 读取演讲的起始时间和中止时间
    for (int i = 0; i < n; i++) {
        a[i].begin = read();
        a[i].end = read();
    }

    // 按结束时间排序
    sort(a, a + n, cmp);

    p = a[n - 1].end;
    int dp[30005] = {0}; // 动态规划数组

    // 动态规划计算最大可能的使用时间
    for (int i = 0; i < n; i++) {
        for (int j = p; j >= a[i].end; j--) {
            dp[j] = max(dp[j], dp[a[i].begin] + a[i].end - a[i].begin);
        }
    }

    cout << dp[p] << endl;

    return 0;
}