C-贪婪的电视观看算法

Question

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

Alex是电视的忠实拥护者。他写下了他感兴趣的所有电视节目今天。他的清单包含n个节目，第三章开始时开始，然后在RI时结束。亚历克斯拥有两台电视。他可以与两台电视同时观看两场不同的节目，但他只能在一台电视上的任何给定时刻观看一场演出。如果一个节目同时结束其他节目开始，那么您无法在一台电视上观看它们。亚历克斯想检查所有n个节目。两台电视足以这样做吗？编写一个程序来帮助亚历克斯找出答案。输入第一行包含一个指示显示数量的整数。下一个n行中的每一行都包含两个整数的开始和结束时间。输出如果Alex只能使用两台电视查看所有节目，则打印"是"（无引号）。否则，打印"否"（没有报价）。

示例输入
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, "%dn", &num);
    for(int i = 0; i < num; i++){
        fscanf(filePtr, "%d, %dn", &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的返回值;
• 即使标记为const。
，尝试修改num即使

解决这些问题也将大有帮助解决您的问题。通常，您应该检查以后可能在下游效果的任何调用，例如：

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

和：

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

---

，顺便说一句，我不确定我了解您的算法是如何工作的。可能值得将其分解为单独的模块，以便更容易理解和调试。

我要采用的方法是解决您感兴趣的所有时间点，在您的情况下，这是从最低1到maximum 5`。

的所有时间点。

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

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

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

使人还可以。