贪心看电视算法

Question

我正在尝试在 C 中实现以下贪心算法：

亚历克斯是电视迷。他写下了所有他感兴趣的电视节目今天。他的列表包含 n 个节目，其中第 i 个节目从时刻 li 开始，到时刻 ri 结束。亚历克斯拥有两台电视。他可以同时用两台电视看两个不同的节目，但他只能在任何给定时刻在一台电视上观看一个节目。如果一场演出在同一时刻结束其他节目开始，那么您将无法在一台电视上观看它们。 Alex 想查看所有 n 个节目。两台电视够吗？编写一个程序来帮助亚历克斯找出答案。输入第一行包含一个整数，表示显示的数量。接下来的 n 行中的每一行都包含两个整数，即第 i 个节目的开始和结束时间。输出如果 Alex 能够仅使用两台电视查看所有节目，则打印 "YES"（不带引号）。否则，打印 "NO"（不带引号）。

输入示例
3
1, 2
2, 3
4、5
输出
是

但是，每当我运行我的实现时，我都会收到分段错误。我确定这是我没有看到的东西，但我似乎无法缩小问题的范围。下面是我的代码：

#include <stdio.h>

int main(){

    const int num;

    int A[num][2]; //should be declared after fscanf

FILE* filePtr = fopen("input2.txt","r");

fscanf(filePtr, "%d\n", &num);

    for(int i = 0; i < num; i++){
        fscanf(filePtr, "%d, %d\n", &A[i][0], &A[i][1]);
    }

    fclose(filePtr);

    int temp[2];

    for(int i = 0; i < num; i++){
        for(int j = 0; j < (num - i) - 1; j++){
            if(A[j][0] > A[j+1][0]){
                temp[0] = A[j][0];
                temp[1] = A[j][1];
                A[j][0] = A[j+1][0];
                A[j][1] = A[j+1][1];
                A[j+1][0] = A[j+1][0];
                A[j+1][1] = A[j+1][1];
            }
        }

    }

    int TV1 = 0, TV2 = 0;
    int currentShow = 0;

    for(int i = A[0][0]; i <= A[num-1][0] && currentShow < num; i++){
        if(i == A[currentShow][0]){
            if(TV1 == 0) TV1 = A[currentShow][1] - A[currentShow][0];
            else if(TV2 == 0) TV2 = A[currentShow][1] - A[currentShow][0];
            else{
                printf("No.\n");
                break;
            }
            currentShow++;
        }

        if(TV1 > 0) TV1--;
        if(TV2 > 0) TV2--;
    }

    if(currentShow == num) printf("Yes.\n");

    return 0;
}

Answer 1

const int num;
int A[num][2];

这是一个比较严重的问题，创建A时num没有设置任何值。这不太可能有好结果。

如果您想使用 num 作为维度说明符，您应该等到您知道它是什么（在第一个 fscanf 之后）。编译器很好，但我很确定它们与我们一样遵守相同的时间规则:-)

还有很多其他事情向我袭来，例如：

不检查 fopen 或 fscanf 的 return 值；
试图修改 num，即使它被标记为 const。

解决这些问题也将大大有助于解决您的问题。您通常应该检查 any 稍后可能产生下游影响的调用，例如：

FILE* filePtr = fopen("input2.txt", "r");
if (filePtr == NULL) {
    fprintf(stderr, "Could not open input file\n");
    return 1;
}

和：

if (fscanf(filePtr, "%d, %d\n", &A[i][0], &A[i][1]) != 2) {
    fprintf(stderr, "Could not get two integers from file\n");
    fclose(filePtr);
    return 1;
}

顺便说一句，我不完全确定我理解你的算法是如何工作的。将它分解成单独的模块可能是值得的，这样更容易理解和调试。

我将采用的方法是计算出您感兴趣的所有时间点，在您的情况下，是从最小值 1 到 maximum5` 的所有时间点。

然后，对于所有这些，计算它出现的持续时间。如果超过两台，那么显然两台电视无法完成这项工作。

从概念的角度来看，您的测试数据将是：

Timepoint  Appears-in:  1-2  2-3  4-5  count
---------  --------------------------  -----
    1                   yes  no   no     1
    2                   yes  yes  no     2
    3                   no   yes  no     1
    4                   no   no   yes    1
    5                   no   no   yes    1

所以那个没问题。

贪心看电视算法

Greedy TV Watching Algorithm

c

algorithm

greedy

segmentation-fault