c++ - 所需的最少出租车(算法)

Question

我正在尝试解决这个问题:

https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/practice-problems/algorithm/minimum-cabs-0798cfa5/description/

我在这里看到了一个解决方案，但我不太明白。

#include <bits/stdc++.h>
using namespace std;
const int MAX = 1500;
int A[MAX];
int main(int argc, char* argv[])
{
    if(argc == 2 or argc == 3) freopen(argv[1], "r", stdin);
    if(argc == 3) freopen(argv[2], "w", stdout);
    ios::sync_with_stdio(false);
    int n, hh1, hh2, mm1, mm2, smins, emins, ans;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> hh1 >> mm1 >> hh2 >> mm2;
        smins = hh1 * 60 + mm1;
        emins = hh2 * 60 + mm2;
        A[smins]++;
        A[emins+1]--;
    }
    ans = A[0];
    for (int i = 1; i < MAX; i++) {
        A[i] += A[i-1];
        ans = max(ans, A[i]);
    }
    cout << ans << endl;
    return 0;

}

谁能给我解释一下这个算法？

Answer 1

给定的解决方案适用于最大重叠间隔。

作者想要计算在任何给定时间点重叠的最大间隔数或范围数。

假设一个时间尺度，它代表时间:

Min time: 00:00 => 代表时间刻度上的0

Max time: 23:59 => 代表时间尺度上的1439

所以，作者使用了一个常量MAX作为1500，从而使得时间尺度为[0, 1500]，满足了我们的要求。

现在，对于我们从输入中获得的每个间隔/范围，作者使用前缀和，从而为范围内的每个时间单位加 1。

例如:假设我的范围是 00:00 到 12:36，那么我将为数组 A 从 0 到 756 的每个索引加 1。

最大前缀和表示所需出租车的最小数量，因为在任何特定时间，1 辆出租车只能分配给 1 个人。

希望这对您有所帮助。如有任何疑问，请随时提出。如果满足您的疑问，请将答案标记为正确。