用c语言和贪心算法解决这个问题:描述 Given N TV programs with each having a begin time and an end time, compute how many TV programs you can watch at most. 输入 There are multiple test cases. The first line of each test case contains an integer N (1<=N<=1000), the number of TV programs. Then N lines follow, with every line containing two integers Bi and Ei (1<=Bi<Ei<=INT_MAX), representing the begin time and end time of TV program i. The inputs terminate at the end of the file (EOF). 输出 For each test case, output a line containing an integer which is the number of TV programs that you can watch at most.
时间: 2024-02-20 20:00:33 浏览: 159
好的,我会为您解答这个问题。首先,这是一个经典的贪心算法问题,我们可以按照结束时间从早到晚对所有电视节目进行排序,然后依次选择结束时间最早的电视节目,并将其结束时间作为下一个选择的起始时间,直到所有电视节目都被选择完。下面是用C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int start;
int end;
} Program;
int cmp(const void* a, const void* b) {
Program* p1 = (Program*)a;
Program* p2 = (Program*)b;
return p1->end - p2->end;
}
int main() {
int n;
while (scanf("%d", &n) != EOF) {
Program* programs = (Program*)malloc(n * sizeof(Program));
for (int i = 0; i < n; i++) {
scanf("%d%d", &programs[i].start, &programs[i].end);
}
qsort(programs, n, sizeof(Program), cmp);
int count = 0, end = 0;
for (int i = 0; i < n; i++) {
if (programs[i].start >= end) {
count++;
end = programs[i].end;
}
}
printf("%d\n", count);
free(programs);
}
return 0;
}
```
代码中,我们定义了一个结构体 `Program` 来存储每个电视节目的开始时间和结束时间。`cmp` 函数是用来比较两个电视节目的结束时间的,用于 `qsort` 排序。在 `main` 函数中,我们使用 `scanf` 读入每个测试用例,然后按照结束时间从早到晚对所有电视节目进行排序。接下来,我们使用 `count` 记录可以观看的电视节目数量,`end` 记录上一个观看的电视节目的结束时间。然后遍历所有电视节目,如果当前电视节目的开始时间大于等于 `end`,则选择该电视节目,并更新 `count` 和 `end`。最后输出 `count` 即可。
希望我的回答对您有帮助!
阅读全文