7-58 会场安排问题 分数 20 作者 陈晓梅 单位 广东外语外贸大学 题目来源：王晓东《算法设计与分析》 假设要在足够多的会场里安排一批活动，并希望使用尽可能少的会场。设计一个有效的 贪心算法进行安排。（这个问题实际上是著名的图着色问题。若将每一个活动作为图的一个 顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小 会场数。） 输入格式: 第一行有 1 个正整数k，表示有 k个待安排的活动。 接下来的 k行中，每行有 2个正整数，分别表示 k个待安排的活动开始时间和结束时间。时间 以 0 点开始的分钟计。 输出格式: 输出最少会场数。 输入样例: 5 1 23 12 28 25 35 27 80 36 50 输出样例: 在这里给出相应的输出。例如： 3

这道题是典型的贪心算法题目，可以使用贪心思想解决。

首先，我们需要将所有的活动按照结束时间从小到大进行排序，这样可以保证每个会场尽量安排更多的活动。

然后，我们从前往后遍历所有的活动，对于每个活动，我们需要找到一个合适的会场。一个会场是合适的，当且仅当该会场中已安排的所有活动的结束时间都早于当前考虑的活动的开始时间。如果当前有多个合适的会场，我们选择其中结束时间最早的那个会场，这样可以保证给后面的活动留出更多的时间。

如果当前没有合适的会场，我们就需要新开一个会场，将当前的活动安排在这个新的会场中。

最后，我们安排的会场总数就是最少会场数。具体实现可以使用一个优先队列来维护每个会场的结束时间，每次取出结束时间最早的会场来安排活动。

代码如下：

相关问题

7-4 两个有序链表合并（新表不含重复元素） 分数 25 作者 陈晓梅 单位 广东外语外贸大学 已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。 要求S3中没有重复元素。

可以使用双指针法，从两个非降序链表的头部开始遍历，比较两个指针所指向的节点的值的大小，将较小的值插入到新的链表S3中，并将相应的指针向后移动一位，重复这个过程直到遍历完两条链表中的所有节点。若两个指针所指向的节点的值相同，则只将其中一个节点插入到新的链表S3中。最后返回合并后的新的非降序链表S3即可。

7-1 利用指针返回多个函数值 分数 30 作者 陈晓梅 单位 广东外语外贸大学 读入n个整数，调用max_min()函数求这n个数中的最大值和最小值。 输入格式: 输入有两行： 第一行是n值； 第二行是n个数。 输出格式: 输出最大值和最小值。 输入样例: 在这里给出一组输入。例如： 5 8 9 12 0 3

以下是实现max_min()函数的代码：

#include <stdio.h>

void max_min(int* arr, int n, int* max, int* min) {
    *max = *min = *arr;
    for (int i = 1; i < n; i++) {
        if (*(arr + i) > *max) {
            *max = *(arr + i);
        }
        if (*(arr + i) < *min) {
            *min = *(arr + i);
        }
    }
}

int main() {
    int n, max, min;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", arr + i);
    }
    max_min(arr, n, &max, &min);
    printf("%d %d", max, min);
    return 0;
}

该程序定义了一个max_min函数，输入参数包括一个整型数组指针arr、数组长度n，以及两个整型指针max和min，用于返回最大值和最小值。在函数中，首先将max和min的初值设为数组第一个元素，然后遍历数组，将每个元素与当前的最大值和最小值进行比较，更新max和min的值。最后，max和min的值通过指针返回到主函数中，并输出。