There is a dual core processor with one queue for each core. There are n processes, where the time to complete the i-th process is denoted by time[i] (0 ≤ i < n). One core holds a "latch" at any moment. When assigning the i-th process, the holder of the latch picks one of two operations:
- The i-th process is assigned to the core c (latch holder), and the latch is given to the other core.
- The i-th process is assigned to the other core, and the latch is retained by core c.
The aim of each core is to have a maximum sum of time of processes with them for better performance. So, while assigning the (i)th process, the core with the latch decides the operation to be performed such that the total sum of time of processes assigned to it is maximized after all the processes are assigned.
Return the sum of time taken by the first process and the second process i.e. S1 and S2 in an array.
Function Description
Complete the function
maximizeSumOfProcessedTimesin the editor.maximizeSumOfProcessedTimeshas the following parameter: int[] time: an array of integers representing the time to complete each process Returnsint[]: an array of two integers representing the sum of time taken by the first and second process respectively
解法
贪心/博弈 DP。设当前 latch 在 core 1，时间 t；若把任务给自己则 latch 翻转；若给对方则 latch 保持。两核都贪婪追求自己累计最大。倒序 DP：f[i][latch] 表示从第 i 个任务开始，当前 latch 持有者的最大累计。g[i][latch] 表示另一方累计。转移：当前 latch 决策"自己或对方"取 f 最大方案。最终返回 [S1, S2]。时间复杂度 O(n)。
from typing import List
def maximizeSumOfProcessedTimes(time: List[int]) -> List[int]:
n = len(time)
# f[i] = (latch holder's max, other's value) when latch is at "current holder" starting from i
# We solve by computing dp[i] = pair (latch_sum, other_sum) assuming optimal play.
dp_latch = [0] * (n + 1)
dp_other = [0] * (n + 1)
for i in range(n - 1, -1, -1):
# option A: take it (latch goes to other)
a_latch = time[i] + dp_other[i + 1]
a_other = dp_latch[i + 1]
# option B: give to other (latch stays)
b_latch = dp_latch[i + 1]
b_other = time[i] + dp_other[i + 1]
if a_latch >= b_latch:
dp_latch[i] = a_latch; dp_other[i] = a_other
else:
dp_latch[i] = b_latch; dp_other[i] = b_other
return [dp_latch[0], dp_other[0]]class Solution {
int[] maximizeSumOfProcessedTimes(int[] time) {
int n = time.length;
long[] dpL = new long[n + 1], dpO = new long[n + 1];
for (int i = n - 1; i >= 0; i--) {
long aL = time[i] + dpO[i + 1], aO = dpL[i + 1];
long bL = dpL[i + 1], bO = time[i] + dpO[i + 1];
if (aL >= bL) { dpL[i] = aL; dpO[i] = aO; }
else { dpL[i] = bL; dpO[i] = bO; }
}
return new int[]{(int) dpL[0], (int) dpO[0]};
}
}class Solution {
public:
vector<int> maximizeSumOfProcessedTimes(vector<int>& time) {
int n = time.size();
vector<long long> dpL(n + 1, 0), dpO(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
long long aL = time[i] + dpO[i + 1], aO = dpL[i + 1];
long long bL = dpL[i + 1], bO = time[i] + dpO[i + 1];
if (aL >= bL) { dpL[i] = aL; dpO[i] = aO; }
else { dpL[i] = bL; dpO[i] = bO; }
}
return {(int) dpL[0], (int) dpO[0]};
}
};Given n developers, each developer i is described by two values lowerSkill[i] and higherSkill[i], the range of skill levels they are willing to work at. A team operates at a single skill level; each developer must join one team whose level lies in their range. Find the minimum number of teams needed — equivalently, the maximum number of intervals overlapping at any single point.
Example 1
Input:
lowerSkill = [1, 3, 2, 2, 2]
higherSkill = [2, 2, 1, 1, 3]Output:
3Explanation: At skill level 2, four intervals overlap, but a partition of 3 teams (e.g., levels 1, 2, 3) covers everyone.
解法
按区间覆盖：将开发者按 [lowerSkill[i], higherSkill[i]] 排序，然后贪心匹配(类似 LC 757 / interval scheduling)。具体：把所有点(端点)扫描线，每次找当前最少需要的"覆盖团队数"。给出经典解法：扫描线计算最大并发开放区间数(这就是输出 3 的意思)。时间复杂度 O(n log n)。
from typing import List
def teamFormation(lowerSkill: List[int], higherSkill: List[int]) -> int:
events = []
for l, h in zip(lowerSkill, higherSkill):
events.append((l, 1))
events.append((h + 1, -1))
events.sort()
cur = peak = 0
for _, d in events:
cur += d
peak = max(peak, cur)
return peakclass Solution {
int teamFormation(int[] lowerSkill, int[] higherSkill) {
int n = lowerSkill.length;
int[][] events = new int[2 * n][2];
for (int i = 0; i < n; i++) {
events[2 * i] = new int[]{lowerSkill[i], 1};
events[2 * i + 1] = new int[]{higherSkill[i] + 1, -1};
}
Arrays.sort(events, (a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);
int cur = 0, peak = 0;
for (int[] e : events) { cur += e[1]; peak = Math.max(peak, cur); }
return peak;
}
}class Solution {
public:
int teamFormation(vector<int>& lowerSkill, vector<int>& higherSkill) {
vector<pair<int, int>> events;
for (int i = 0; i < (int)lowerSkill.size(); i++) {
events.push_back({lowerSkill[i], 1});
events.push_back({higherSkill[i] + 1, -1});
}
sort(events.begin(), events.end());
int cur = 0, peak = 0;
for (auto& [t, d] : events) { cur += d; peak = max(peak, cur); }
return peak;
}
};You are given an array time of process durations. Same dual-core / latch-toggle rules as problem 1: the latch holder decides whether each next process goes to themselves (latch flips) or to the other core (latch stays). Each core plays optimally to maximize its own total time. Return [S1, S2], the totals assigned to core 1 and core 2.
Example 1
Input:
time = [10, 21, 10, 21, 10]Output:
[41, 31]Explanation: Optimal alternating assignment under the latch game yields S1 = 41 and S2 = 31.
解法
与第一题相同的双核博弈，复用 DP 解。时间复杂度 O(n)。
from typing import List
def twoCoreProcessAssignment(time: List[int]) -> List[int]:
n = len(time)
dpL = [0] * (n + 1)
dpO = [0] * (n + 1)
for i in range(n - 1, -1, -1):
aL = time[i] + dpO[i + 1]; aO = dpL[i + 1]
bL = dpL[i + 1]; bO = time[i] + dpO[i + 1]
if aL >= bL: dpL[i], dpO[i] = aL, aO
else: dpL[i], dpO[i] = bL, bO
return [dpL[0], dpO[0]]class Solution {
int[] twoCoreProcessAssignment(int[] time) {
int n = time.length;
long[] dpL = new long[n + 1], dpO = new long[n + 1];
for (int i = n - 1; i >= 0; i--) {
long aL = time[i] + dpO[i + 1], aO = dpL[i + 1];
long bL = dpL[i + 1], bO = time[i] + dpO[i + 1];
if (aL >= bL) { dpL[i] = aL; dpO[i] = aO; }
else { dpL[i] = bL; dpO[i] = bO; }
}
return new int[]{(int) dpL[0], (int) dpO[0]};
}
}class Solution {
public:
vector<int> twoCoreProcessAssignment(vector<int>& time) {
int n = time.size();
vector<long long> dpL(n + 1, 0), dpO(n + 1, 0);
for (int i = n - 1; i >= 0; i--) {
long long aL = time[i] + dpO[i + 1], aO = dpL[i + 1];
long long bL = dpL[i + 1], bO = time[i] + dpO[i + 1];
if (aL >= bL) { dpL[i] = aL; dpO[i] = aO; }
else { dpL[i] = bL; dpO[i] = bO; }
}
return {(int) dpL[0], (int) dpO[0]};
}
};