有一个演讲大厅需要我们管理，演讲者们事先定好了需要演讲的起始时间和中止时间。 我们想让演讲大厅得到最大可能的使用。我们要接受一些预定而拒绝其他的预定，目标是使 演讲者使用大厅的时间最长。假设在某一时刻一个演讲结束，另一个演讲就可以立即开始。 请计算演讲大厅最大可能的使用时间。 输入格式: 第一行为一个整数 N，N≤5000，表示申请的数目。 以下 n 行每行包含两个整数 p，k，1 ≤ p < k ≤ 30000，表示这个申请的起始时间和中止时间。 输出格式: 一个整数，表示大厅最大可能的使用时间。

这是一个经典的贪心算法问题。首先根据演讲的结束时间排序，然后依次将能安排的演讲加入安排列表中。如果当前演讲的起始时间晚于已安排演讲的结束时间，则可以安排该演讲。否则需要舍弃该演讲。最后输出已安排演讲的总时间即可。

以下是Python实现代码：

n = int(input())
talks = []
for i in range(n):
    start, end = map(int, input().split())
    talks.append((start, end))
talks.sort(key=lambda x: x[1])  # 按结束时间排序
ans = 0
end_time = 0
for talk in talks:
    if talk[0] >= end_time:
        # 可以安排该演讲
        ans += 1
        end_time = talk[1]
print(ans)

时间复杂度为 $O(n\log n)$，因为需要排序。

相关问题

用c语言动态规划写下面题目有一个演讲大厅需要我们管理，演讲者们事先定好了需要演讲的起始时间和中止时间。 我们想让演讲大厅得到最大可能的使用。我们要接受一些预定而拒绝其他的预定，目标是使 演讲者使用大厅的时间最长。假设在某一时刻一个演讲结束，另一个演讲就可以立即开始。 请计算演讲大厅最大可能的使用时间。 输入格式: 第一行为一个整数 N，N≤5000，表示申请的数目。 以下 n 行每行包含两个整数 p，k，1 ≤ p < k ≤ 30000，表示这个申请的起始时间和中止时间。 输出格式: 一个整数，表示大厅最大可能的使用时间。 输入样例1: 5 0 3 2 6 5 7 1 5 5 9 输出样例1: 8

以下是C语言动态规划代码实现：

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start, end;
} Meeting;

int cmp(const void *a, const void *b) {
    Meeting *ma = (Meeting *)a, *mb = (Meeting *)b;
    return ma->end - mb->end;
}

int main() {
    int n;
    scanf("%d", &n);
    Meeting *meetings = (Meeting *)malloc(n * sizeof(Meeting));
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &meetings[i].start, &meetings[i].end);
    }

    qsort(meetings, n, sizeof(Meeting), cmp);

    int *dp = (int *)calloc(n, sizeof(int));
    dp[0] = meetings[0].end - meetings[0].start;
    int max_time = dp[0];
    for (int i = 1; i < n; i++) {
        dp[i] = meetings[i].end - meetings[i].start;
        for (int j = i - 1; j >= 0; j--) {
            if (meetings[i].start >= meetings[j].end) {
                dp[i] = dp[j] + meetings[i].end - meetings[i].start;
                break;
            }
        }
        if (dp[i] > max_time) {
            max_time = dp[i];
        }
    }

    printf("%d\n", max_time);

    free(meetings);
    free(dp);
    return 0;
}

注释说明：

- 与前一个问题相似，首先定义结构体 `Meeting`，表示每个预定的起始时间和中止时间。
- 定义比较函数 `cmp`，用于将所有预定按照结束时间从小到大排序。
- 读入预定数据，并按照结束时间从小到大排序。
- 定义动态规划数组 `dp`，表示前 `i` 个预定中，选择第 `i` 个预定时最多能使用的时间，即当前预定的使用时间加上前面最多能使用的时间。
- 初始化 `dp[0] = meetings[0].end - meetings[0].start`，表示第一个预定的最大使用时间为该预定的时间长度。
- 对于每个 `i`，从 `i-1` 到 0 的范围内寻找能与第 `i` 个预定不冲突的最大 `j`，然后更新 `dp[i] = dp[j] + meetings[i].end - meetings[i].start`。
- 在每次更新 `dp[i]` 时，记录当前 `dp` 数组中的最大值 `max_time`。
- 最后输出 `max_time` 即为答案。

时间复杂度为 $O(n^2)$，可以通过本题，但对于数据量较大的情况下可能会超时。可以使用其他算法进行优化。