间隔时间表问题关于从每个间隔选择相同的时间长度

Question

我对间隔时间表问题感到困惑，问题描述如下：

描述：兰兰有N个朋友。每个星期天，兰兰都必须和他的朋友一起玩。第i个朋友可以在时间b（包括a和b）中与Lanran一起玩。然而，兰兰必须与他的每个朋友一起玩相同的时间。兰兰希望尽可能地和他的朋友一起玩。但他非常愚蠢。所以他请求你的帮助来计算他和他的每个朋友一起玩的最长时间。

输入第一行包含一个整数N.接下来的N（N <= 5000）行中的每一行包含两个整数a和b（1 <= a，b <= 10000），它们显示了第i个朋友的时间间隔。

输出输出一个整数，显示Lanran可以与他的每个朋友一起玩的最长时间。

我认为这是一个贪婪的问题，我选择最小的时间朋友，这是已经播放的时间+可能的播放时间直到朋友的b，并在第i秒与他一起玩。这是代码：

#include <bits/stdc++.h>

using namespace std;
const int N = 5010;
int n, s[N], e[N], cnt[N], me;

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int low, int high) {
    int pivot = s[high];
    int i = (low - 1);

    for (int j = low; j <= high - 1; j++) {
        if (s[j] <= pivot) {
            i++;
            swap(&s[i], &s[j]);
            swap(&e[i], &e[j]);
        }
    }
    swap(&s[i + 1], &s[high]);
    swap(&e[i + 1], &e[high]);
    return (i + 1);
}

void quickSort(int low, int high) {
    if (low < high) {
        int pi = partition(low, high);
        quickSort(low, pi - 1);
        quickSort(pi + 1, high);
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &s[i], &e[i]);
        if (e[i] < s[i]) { printf("0\n"); return 0; }
        if (e[i] > me) me = e[i];
    }
    quickSort(0, n - 1);
    for (int i = 1; i <= me; ++i) {
        int id = -1, mi = 0x7fffffff;
        for (int j = 0; j < n; ++j) {
            if (s[j] > i || i > e[j]) continue;
            if (cnt[j] + e[j] - i + 1 < mi) { id = j; mi = cnt[j] + e[j] - i + 1; }
        }
        ++cnt[id];
    }
    int ans = 0x7fffffff;
    for (int i = 0; i < n; ++i) if (cnt[i] < ans) ans = cnt[i];
    printf("%d\n", ans);
    return 0;
}

那么我做错了什么？我在10个测试用例中得到了7个错误答案。

Answer 1

看起来它与标准活动选择问题相同。我粘贴相关的标准算法。你可以找到wiki：https://en.wikipedia.org/wiki/Activity_selection_problem。贪婪迭代活动选择器（A，s，f）：

Sort A by finish times stored in f

S = {A[1]} 
k = 1

n = A.length

for i = 2 to n:
   if s[i] ≥ f[k]: 
       S = S U {A[i]}
       k = i

return S