[LeetCode] 826. Most Profit Assigning Work

문제

작업마다 difficulty[i]와 profit[i]가 주어지고, 워커마다 능력치 worker[j]가 주어집니다.
워커는 자신의 능력치 이하인 작업 중 하나만 맡을 수 있고, 같은 작업을 여러 워커가 맡아도 됩니다.
얻을 수 있는 총 이익의 최댓값을 구합니다.

• 작업 수, 워커 수 모두 최대 10^4

첫 시도에서 틀린 부분

난이도를 키로 Map<difficulty, profit>을 만들고, 워커마다 정렬된 난이도를 처음부터 훑으며 max를 찾았습니다.

const profitMap = new Map<number, number>();
for (let i = 0; i < n; i++) profitMap.set(difficulty[i], profit[i]);

두 가지가 무너졌습니다.

1. 난이도는 고유 키가 아닙니다. difficulty = [1, 1], profit = [10, 1]이면 Map이 10을 덮어써서 1만 남습니다.
2. 워커마다 다시 스캔하면 O(작업 × 워커) = 10^8이라 시간 초과입니다.

접근

워커마다 "내 능력 이하인 작업 중 최고 이익"을 묻는 질문이므로, 이 답을 미리 만들어 두면 됩니다.

1. (난이도, 이익) 쌍으로 묶어 난이도 오름차순 정렬
2. prefix max: 왼쪽부터 훑으며 job[i][1] = max(내 이익, 왼쪽 값)으로 덮어씁니다. 끝나면 job[i][1]의 의미가 "난이도 job[i][0] 이하 작업 중 최고 이익"으로 바뀝니다.
3. 워커마다 이분 탐색으로 "능력을 처음 넘는 작업 위치 low"를 찾고, job[low - 1][1]을 더합니다.

정렬 후:      (2,10) (4,3)  (6,7)  (8,20) (10,5)
prefix max:   (2,10) (4,10) (6,10) (8,20) (10,20)

ability 7  → low = 3 → job[2] = 10
ability 50 → low = 5 → job[4] = 20
ability 1  → low = 0 → 할 수 있는 작업 없음, 0

코드

function maxProfitAssignment(difficulty: number[], profit: number[], worker: number[]): number {
    const n = difficulty.length;

    const job = difficulty.map((diff, idx) => [diff, profit[idx]]).sort((a, b) => a[0] - b[0]);
    for (let i = 1; i < n; i++) job[i][1] = Math.max(job[i][1], job[i - 1][1]);

    let totalProfit = 0;
    for (const ability of worker) {
        let low = 0;
        let high = n;
        while (low < high) {
            const mid = Math.floor((low + high) / 2);
            if (job[mid][0] > ability) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        if (low > 0) totalProfit += job[low - 1][1];
    }

    return totalProfit;
}

짚고 갈 점

• high = n이어야 합니다. n - 1로 두면 모든 작업을 할 수 있는 워커가 마지막 작업을 못 받습니다. "하나도 안 넘음"이라는 답(= n)이 탐색 범위에 들어가야 합니다.
• low > 0 체크는 가장 쉬운 작업조차 못 하는 워커를 거릅니다. 이때 job[-1]은 undefined입니다.
• 복잡도: 정렬 O(n log n) + 워커마다 이분 탐색 O(m log n)