Agoda

— / 4已做

01Maximize Sum of Processed Times

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 maximizeSumOfProcessedTimes in the editor. maximizeSumOfProcessedTimes has the following parameter:
int[] time: an array of integers representing the time to complete each process Returns int[]: 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]};
    }
};

02Team Formation

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:

Explanation: 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 peak

class 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;
    }
};

03Two-Core Process Assignment

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]};
    }
};

04Unique Digits in Range

Given a range [a, b] (inclusive), return the count of integers in that range whose decimal digits are all distinct (no repeated digit).

Example 1

Input:

a = 5
b = 11

Output:

Explanation: ^o^

Pro解法 · 三语代码 · 复杂度分析

边界讨论 + 面试官追问 · $98 / 一年解锁

Pro 会员

解锁全部 1 道题的解法

题面你已经看到了 — 解法 + 三语代码 + 复杂度推导 + 边界讨论, Pro 解锁.

Pro 解锁全部

📚1000+ 道真实北美 OA, Python / Java / C++ 三语题解
📊个人 dashboard + 进度可视化 + 14 天活跃图
📝题目笔记跨设备同步 + 个人复盘库
🔓随时取消下次续费, Stripe Customer Portal 自助管理

$12/月($98/年, 一次付清省 32%)

≈ 北美 SWE 工资 10 分钟 · LeetCode Premium $35/月的 23%

立即解锁 $98/年已是会员, 去登录