题目描述

某实验室计算机待处理任务以 [start,end,period] 格式记于二维数组 tasks，表示完成该任务的时间范围为起始时间 start 至结束时间 end 之间，需要计算机投入 period 的时长，注意：

1. period 可为不连续时间。
2. 首尾时间均包含在内。

处于开机状态的计算机可同时处理任意多个任务，请返回电脑最少开机多久，可处理完所有任务。

样例

输入：tasks = [[1,3,2],[2,5,3],[5,6,2]]
输出：4
解释：
tasks[0] 选择时间点 2、3；
tasks[1] 选择时间点 2、3、5；
tasks[2] 选择时间点 5、6；
因此计算机仅需在时间点 2、3、5、6 四个时刻保持开机即可完成任务。

输入：tasks = [[2,3,1],[5,5,1],[5,6,2]]
输出：3
解释：
tasks[0] 选择时间点 2 或 3；
tasks[1] 选择时间点 5；
tasks[2] 选择时间点 5、6；
因此计算机仅需在时间点 2、5、6 或 3、5、6 三个时刻保持开机即可完成任务。

限制

• 2 <= tasks.length <= 10^5
• tasks[i].length == 3
• 0 <= tasks[i][0] <= tasks[i][1] <= 10^9
• 1 <= tasks[i][2] <= tasks[i][1] - tasks[i][0] + 1

算法1

(贪心，二分，栈) $O(n \log n)$

1. 将任务按照结束时间从小到大排序。
2. 对于每个任务，都尽量将任务向后安排。
3. 具体地，维护一个数组，表示需要单独加时间的任务，以及加时间任务的开始（左）、结束（右）时间点。再维护这些任务时间的前缀和。注意，这里新维护的单独时间的任务区间不会有重叠。
4. 初始时，插入空任务当做哨兵，开始时间为 0，结束时间为 -1，时长为 0。
5. 对于当前任务，二分查找，找到尽可能小的任务右端点，使得当前任务左端点大于等于这个右端点。
6. 通过前缀和计算出可以和之前任务并行的时间，扣除这些时间。
7. 如果剩余时间等于 0，则当前任务无需再加时间。
8. 如果剩余时间大于 0，则需要单独加时间，此时需要判断是否会跨过已有加时间的任务，避免重叠。如果和最后一个单独加时间的任务有重叠，需要将最后一个任务出栈。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 对于每个任务，二分的时间复杂度为 $O(\log n)$。
• 每个任务最多进栈一次，出栈一次。
• 故总时间复杂度为 $O(n \log n)$。

空间复杂度

• 需要 $O(n)$ 的额外空间存储排序时的系统栈空间，以及临时数据结构。

C++ 代码

#define N 100010

class Solution {
private:
    int sum[N], tl[N], tr[N];

public:
    int processTasks(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end(),
            [](const vector<int> &t1, const vector<int> &t2) {
                return t1[1] < t2[1];
            }
        );

        const int n = tasks.size();

        int m = 1;
        sum[0] = 0; tl[0] = 0; tr[0] = -1;

        for (int i = 0; i < n; i++) {
            int l = 1, r = m;

            // 二分找到左端点对应的任务
            while (l < r) {
                int mid = (l + r) >> 1;
                if (tasks[i][0] <= tr[mid]) r = mid;
                else l = mid + 1;
            }

            // 处理前序任务时，可以并行处理当前任务的时间
            if (l < m)
                tasks[i][2] = max(0, tasks[i][2]
                    - (sum[m - 1] - sum[l])
                    - (tr[l] - max(tl[l], tasks[i][0]) + 1));

            // 之前的任务并行处理后无需单独处理当前任务
            if (tasks[i][2] == 0)
                continue;

            // 还需要给当前任务单独加时间
            while (m > 0) {
                if (tasks[i][2] <= tasks[i][1] - tr[m - 1]) {
                    // 没有覆盖到最后一个任务
                    tl[m] = tasks[i][1] - tasks[i][2] + 1;
                    tr[m] = tasks[i][1];
                    sum[m] = sum[m - 1] + tasks[i][2];
                    m++;
                    break;
                }

                // 覆盖到了最后一个任务，最后一个任务出栈
                tasks[i][2] += tr[m - 1] - tl[m - 1] + 1;
                m--;
            }
        }

        return sum[m - 1];
    }
};

算法2

(贪心，单调队列) $O(n \log n)$

1. 每个任务都有一个最迟开始时间。假如现在有一堆任务，必定是先做最迟开始时间最早的任务。
2. 如果有若干个同时进行中的任务（即区间有重叠），系统运行 $w$ 时刻，所有进行中的任务的最迟开始时间会后推 $w$。
3. 将任务按照开始时间从小到大排序。使用小跟堆维护任务池（即当前同时进行的任务）中，拥有最小的最迟开始时间的任务。
4. 逐一加入每个任务，对于当前任务 $T$ （其左端点为 $t_s$）和当前任务池中拥有最小的最迟开始时间的任务 $T’$（其最迟开始时间为 $t_s’$），$t_s’ + offset - 1 < t_s - 1$，则说明任务 $T$ 可以先开机运行 $w$ 时间，且 $w$ 时间不和任务 $T$ 并行。
5. 其中 $w = \min(t_e’, t_s - 1) - (t_s’ + offset - 1)$，$offset$ 为当前任务池中已经进行的时间。$ans$ 累加 $w$，$offset$ 也累加 $w$。
6. 如果不满足这个条件，说明当前任务可以加入到任务池中一起开始并行了。
7. 加入到任务池中时，需要抵消掉已有 $offset$ 的影响，所以任务 $T$ 的最迟开始时间可以设为 $t_e - p + 1 - offset$。

时间复杂度

• 排序的时间复杂度为 $O(n \log n)$。
• 对于每个任务，最多进堆一次，出堆一次

空间复杂度

• 需要 $O(n)$ 的额外空间存储排序时的系统栈空间，以及临时数据结构。

C++ 代码

struct Task {
    int start, end;
    Task(int start, int end) {
        this->start = start;
        this->end = end;
    }

    bool operator < (const Task &t) const {
        return start > t.start;
    }
};

class Solution {
public:
    int processTasks(vector<vector<int>>& tasks) {
        sort(tasks.begin(), tasks.end());
        tasks.push_back({INT_MAX, INT_MAX - 1, 0});

        const int n = tasks.size();
        priority_queue<Task> heap;

        int ans = 0, offset = 0;

        for (int i = 0; i < n; i++) {
            while (!heap.empty() && heap.top().start + offset < tasks[i][0]) {
                if (heap.top().start + offset - 1 >= heap.top().end) heap.pop();
                else {
                    int w = min(heap.top().end, tasks[i][0] - 1)
                        - (heap.top().start + offset - 1);
                    ans += w;
                    offset += w;
                }
            }

            heap.push(Task(tasks[i][1] - tasks[i][2] + 1 - offset, tasks[i][1]));
        }

        return ans;
    }
};