Given an array taskMemory of n positive integers representing memory required for each task, an array taskType of n positive integers representing task types, and an integer maxMemory, find the minimum time required to process all tasks.
Each task takes 1 unit of time. The server can process at most 2 tasks in parallel only if they are the same type and together require no more than maxMemory units.
Example: n=4, taskMemory=[7,2,3,9], taskType=[1,2,1,3], maxMemory=10 → 3. Group by type: type 1 = [7,3] pair under 10 → 1 unit; type 2 = [2] → 1 unit; type 3 = [9] → 1 unit; total 3.
Constraints
1 ≤ n ≤ 2×10⁵, 1 ≤ maxMemory, taskMemory[i] ≤ 10⁹, 1 ≤ taskType[i] ≤ 10⁹.
解法
按类型分桶，每组内排序后双指针配对(最小 + 最大)使其和 ≤ maxMemory。复杂度 O(N log N)。
from collections import defaultdict
def getMinTime(taskMemory, taskType, maxMemory):
groups = defaultdict(list)
for m, t in zip(taskMemory, taskType):
groups[t].append(m)
time = 0
for arr in groups.values():
arr.sort()
l, r = 0, len(arr) - 1
while l < r:
if arr[l] + arr[r] <= maxMemory:
time += 1
l += 1
r -= 1
else:
time += 1
r -= 1
if l == r:
time += 1
return timeclass Solution {
static long getMinTime(int[] mem, int[] type, int maxMem) {
Map<Integer, List<Integer>> groups = new HashMap<>();
for (int i = 0; i < mem.length; i++)
groups.computeIfAbsent(type[i], k -> new ArrayList<>()).add(mem[i]);
long time = 0;
for (List<Integer> g : groups.values()) {
Collections.sort(g);
int l = 0, r = g.size() - 1;
while (l < r) {
if (g.get(l) + g.get(r) <= maxMem) { time++; l++; r--; }
else { time++; r--; }
}
if (l == r) time++;
}
return time;
}
}long long getMinTime(vector<int>& mem, vector<int>& type, int maxMem) {
unordered_map<int, vector<int>> groups;
for (size_t i = 0; i < mem.size(); i++) groups[type[i]].push_back(mem[i]);
long long time = 0;
for (auto& [_, g] : groups) {
sort(g.begin(), g.end());
int l = 0, r = (int)g.size() - 1;
while (l < r) {
if (g[l] + g[r] <= maxMem) { time++; l++; r--; }
else { time++; r--; }
}
if (l == r) time++;
}
return time;
}Given an array arr of n non-negative integers and an array power of k integers where k is an even number, perform the following operations:
- Select two integers
iandjsuch that0 ≤ i < j < length of power. In each operation,iandjare selected independently. - If
power[i] ≤ power[j], add the sum of the subarrayarr[power[i] .. power[j]]to the power. - If
power[i] > power[j], add the sum of the subarrayarr[power[j] .. power[i]]to the power. - Delete the i-th and j-th elements from
power, reducing its length by 2.
Starting with 0 initial power, maximize the final power after exactly k/2 operations. Return the maximum power possible modulo 10⁹+7.
Example: arr = [3, 5, 6, 0, 7], power = [3, 1, 0, 2], k = 4 → 25.
解锁全部 1 道题的解法
题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.
- 📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
- 📊个人 dashboard + 进度可视化 + 14 天活跃图
- 📝题目笔记跨设备同步 + 个人复盘库
- 🔓随时取消下次续费, Stripe Customer Portal 自助管理