LCP 32-批量处理任务

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 17:01:06 2023-09-13 17:01:06 Updated    

某实验室计算机待处理任务以 [start,end,period] 格式记于二维数组 tasks，表示完成该任务的时间范围为起始时间 start
至结束时间 end 之间，需要计算机投入 period 的时长，注意： 1. period 可为不连续时间 2. 首尾时间均包含在内
处于开机状态的计算机可同时处理任意多个任务，请返回电脑最少开机多久，可处理完所有任务。 示例 1： >输入：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 四个时刻保持开机即可完成任务。 示例
2： >输入：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

按照右端点排序。

提示 2

对于 tasks}[i] 来说，它右侧的任务要么和它没有交集，要么包含它的区间后缀。

提示 3

遍历排序后的任务，先统计区间内的已有的电脑运行时间点，如果个数小于 duration，则需要新增时间点。根据提示 2，尽量把新增的时间点安排在区间 [\textit{start},\textit{end}] 的后缀上，这样下一个区间就能统计到更多已有的时间点。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 会超时/超内存的暴力代码
class Solution:
    def processTasks(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda t: t[1])
        run = [False] * (tasks[-1][1] + 1)
        for start, end, d in tasks:
            d -= sum(run[start:end + 1])  # 去掉运行中的时间点
            if d > 0:
                for i in range(end, start - 1, -1):  # 剩余的 d 填充区间后缀
                    if run[i]: continue
                    run[i] = True
                    d -= 1
                    if d == 0: break
        return sum(run)
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 会超时/超内存的暴力代码
class Solution {
    public int processTasks(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
        int ans = 0;
        var run = new boolean[tasks[tasks.length - 1][1] + 1];
        for (var t : tasks) {
            int start = t[0], end = t[1], d = t[2];
            for (int i = start; i <= end; ++i)
                if (run[i]) --d;  // 去掉运行中的时间点
            for (int i = end; d > 0; --i) // 剩余的 d 填充区间后缀
                if (!run[i]) {
                    run[i] = true;
                    --d;
                    ++ans;
                }
        }
        return ans;
    }
}
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 会超时/超内存的暴力代码
class Solution {
    bool run[(int) 1e9 + 1];
public:
    int processTasks(vector<vector<int>> &tasks) {
        sort(tasks.begin(), tasks.end(), [](auto &a, auto &b) {
            return a[1] < b[1];
        });
        int ans = 0;
        for (auto &t : tasks) {
            int start = t[0], end = t[1], d = t[2];
            for (int i = start; i <= end; ++i)
                d -= run[i]; // 去掉运行中的时间点
            for (int i = end; d > 0; --i) // 剩余的 d 填充区间后缀
                if (!run[i]) {
                    run[i] = true;
                    --d;
                    ++ans;
                }
        }
        return ans;
    }
};
[sol1-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 会超时/超内存的暴力代码
func processTasks(tasks [][]int) (ans int) {
	sort.Slice(tasks, func(i, j int) bool { return tasks[i][1] < tasks[j][1] })
	run := make([]bool, tasks[len(tasks)-1][1]+1)
	for _, t := range tasks {
		start, end, d := t[0], t[1], t[2]
		for _, b := range run[start : end+1] { // 去掉运行中的时间点
			if b {
				d--
			}
		}
		for i := end; d > 0; i-- { // 剩余的 d 填充区间后缀
			if !run[i] {
				run[i] = true
				d--
				ans++
			}
		}
	}
	return
}

复杂度分析

  • 时间复杂度：O(nU)，其中 n 为 tasks 的长度，U=\max(\textit{end}_i)。
  • 空间复杂度：O(U)。

优化

前置知识：二分查找

见【基础算法精讲 04】 。

思路

由于每次都是从右到左新增时间点，相当于把若干右侧的区间合并成一个大区间，因此可以用栈来优化。

栈中保存闭区间的左右端点，以及从栈底到栈顶的区间长度之和（类似前缀和）。

合并前先在栈中二分查找左端点所在区间，由于我们保存了长度之和，所以可以算出 [\textit{start},\textit{end}] 范围内的运行中的时间点。

如果还需要新增时间点，那么就从右到左合并，具体细节见代码。

[sol3-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def processTasks(self, tasks: List[List[int]]) -> int:
        tasks.sort(key=lambda t: t[1])
        st = [(-2, -2, 0)]  # 闭区间左右端点，栈底到栈顶的区间长度的和
        for start, end, d in tasks:
            _, r, s = st[bisect_left(st, (start,)) - 1]
            d -= st[-1][2] - s  # 去掉运行中的时间点
            if start <= r:  # start 在区间 st[i] 内
                d -= r - start + 1  # 去掉运行中的时间点
            if d <= 0: continue
            while end - st[-1][1] <= d:  # 剩余的 d 填充区间后缀
                l, r, _ = st.pop()
                d += r - l + 1  # 合并区间
            st.append((end - d + 1, end, st[-1][2] + d))
        return st[-1][2]
[sol3-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
    public int processTasks(int[][] tasks) {
        Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
        var st = new ArrayList<int[]>();
        st.add(new int[]{-2, -2, 0}); // 闭区间左右端点，栈底到栈顶的区间长度的和
        for (var t : tasks) {
            int start = t[0], end = t[1], d = t[2];
            var e = st.get(lowerBound(st, start) - 1);
            d -= st.get(st.size() - 1)[2] - e[2]; // 去掉运行中的时间点
            if (start <= e[1]) // start 在区间 st[i] 内
                d -= e[1] - start + 1; // 去掉运行中的时间点
            if (d <= 0) continue;
            while (end - st.get(st.size() - 1)[1] <= d) { // 剩余的 d 填充区间后缀
                e = st.remove(st.size() - 1);
                d += e[1] - e[0] + 1; // 合并区间
            }
            st.add(new int[]{end - d + 1, end, st.get(st.size() - 1)[2] + d});
        }
        return st.get(st.size() - 1)[2];
    }

    // 开区间写法
    private int lowerBound(List<int[]> st, int target) {
        int left = -1, right = st.size(); // 开区间 (left, right)
        while (left + 1 < right) { // 区间不为空
            // 循环不变量：
            // st[left] < target
            // st[right] >= target
            int mid = (left + right) >>> 1;
            if (st.get(mid)[0] < target)
                left = mid; // 范围缩小到 (mid, right)
            else
                right = mid; // 范围缩小到 (left, mid)
        }
        return right; // 或者 left+1
    }
}
[sol3-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int processTasks(vector<vector<int>> &tasks) {
        sort(tasks.begin(), tasks.end(), [](auto &a, auto &b) {
            return a[1] < b[1];
        });
        vector<tuple<int, int, int>> st{ {-2, -2, 0} }; // 闭区间左右端点，栈底到栈顶的区间长度的和
        for (auto &t : tasks) {
            int start = t[0], end = t[1], d = t[2];
            auto[_, r, s] = *--lower_bound(st.begin(), st.end(), start, [](const auto &a, int b) {
                return get<0>(a) < b;
            });
            d -= get<2>(st.back()) - s; // 去掉运行中的时间点
            if (start <= r) // start 在区间 st[i] 内
                d -= r - start + 1; // 去掉运行中的时间点
            if (d <= 0) continue;
            while (end - get<1>(st.back()) <= d) { // 剩余的 d 填充区间后缀
                auto[l, r, _] = st.back();
                d += r - l + 1; // 合并区间
                st.pop_back();
            }
            st.emplace_back(end - d + 1, end, get<2>(st.back()) + d);
        }
        return get<2>(st.back());
    }
};
[sol3-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func processTasks(tasks [][]int) int {
	sort.Slice(tasks, func(i, j int) bool { return tasks[i][1] < tasks[j][1] })
	type tuple struct{ l, r, s int }
	st := []tuple{ {-2, -2, 0} } // 闭区间左右端点，栈底到栈顶的区间长度的和
	for _, p := range tasks {
		start, end, d := p[0], p[1], p[2]
		i := sort.Search(len(st), func(i int) bool { return st[i].l >= start }) - 1
		d -= st[len(st)-1].s - st[i].s // 去掉运行中的时间点
		if start <= st[i].r { // start 在区间 st[i] 内
			d -= st[i].r - start + 1 // 去掉运行中的时间点
		}
		if d <= 0 {
			continue
		}
		for end-st[len(st)-1].r <= d { // 剩余的 d 填充区间后缀
			top := st[len(st)-1]
			st = st[:len(st)-1]
			d += top.r - top.l + 1 // 合并区间
		}
		st = append(st, tuple{end - d + 1, end, st[len(st)-1].s + d})
	}
	return st[len(st)-1].s
}

复杂度分析

  • 时间复杂度：O(n\log n)，其中 n 为 tasks 的长度。
  • 空间复杂度：O(n)。
 Comments
On this page
LCP 32-批量处理任务
  1. 提示 1
  2. 提示 2
  3. 提示 3
  4. 复杂度分析
  • 优化
    1. 前置知识：二分查找
    2. 思路
    3. 复杂度分析