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

Question

我纠结一道interval schedule问题，问题描述如下:

Description: Lanran has N friends. Every Sunday, Lanran has to play with his friends. The i-th friend can play with Lanran from time a to time b (a and b are included). However, Lanran has to play with each of his friends for the same amount of time. Lanran wants to play with his friends as long as possible. But he is very stupid. So he asks for your help to calculate the maximum time he can play with each of his friends.

Input The first line contains one integer N. Each of the next N (N <= 5000) lines contains two integers a and b (1 <= a, b <= 10000), which show the time interval of the i-th friend.

Output Output a single integer, shows the maximum time Lanran can play with each of his friends.

我认为这是一个贪婪的问题，我选择了最少时间的 friend ，也就是 friend 已经玩过的时间 + 可能玩到 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

看起来与标准事件选择问题相同。我正在粘贴相关的标准算法。你可以找到维基: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