Skip to content

826.most-profit-assigning-work.md

Latest commit

 

History

History
198 lines (159 loc) · 11.5 KB

826.most-profit-assigning-work.md

File metadata and controls

198 lines (159 loc) · 11.5 KB

826. Most Profit Assigning Work

Hints

  • Try sorting both the jobs by difficulty and the workers by ability to simplify the matching process.
  • For each worker, you only need to consider jobs with difficulty less than or equal to their ability.
  • Can you preprocess or maintain the maximum profit up to each difficulty level?
  • Think about how to efficiently find the best job for each worker without checking all jobs every time.

Breakdowns

  1. How do we efficiently match each worker to the best job they can do?

Sort jobs by difficulty, and for each worker, find the job with the highest profit that does not exceed their ability.

  1. How can we avoid repeatedly scanning all jobs for each worker?

By sorting both jobs and workers, and using either binary search or two pointers, we can process both lists in a single pass or with efficient lookups.

  1. How do we handle jobs with higher difficulty but lower profit?

Precompute the maximum profit up to each difficulty, so we always pick the best available job for any ability.

Key Insights

  • The core of the problem is to assign each worker the most profitable job they can do, i.e., the job with the highest profit among those with difficulty ≤ their ability.

題目的本質：對每個人找到一份他能做的工作中 利潤最大的那一個, 然後加總起來。

  • Sorting jobs (and/or workers) by difficulty allows us to process them in increasing order.
  • By precomputing the maximum profit up to each difficulty, we ensure that for any ability, we can quickly find the best job.
  • Two pointers intuition:
    • As both jobs and workers are sorted, we can use one pointer to iterate through jobs and another through workers. For each worker, we advance the job pointer as long as the job's difficulty is within the worker's ability, updating the maximum profit seen so far. This way, each job and worker is only processed once, making the approach efficient.
    • The key observation is that as worker ability increases, the set of jobs they can do only grows (monotonicity). Thus, we never need to "go back" to earlier jobs for later workers.
    • This approach is especially powerful when both lists are monotonic, as it allows us to avoid redundant work and achieve linear time after sorting.

講題練習：我們的目標是，對每個人找到一份他能夠勝任的最賺錢的工作，然後累加所有人的利潤總和。

  • 我們先將工作依照 difficulty 排序，這樣我們可以依照門檻遞增處理。
  • 接下來，針對每個 difficulty 做一次預處理，計算 到目前 difficulty 為止，能夠獲得的最大利潤，也就是 maxProfitAtDifficulty[i] = maxOf(job[0..i].profit)。
    • 我們工作照難度排序，但利潤可能不是呈現遞增的現象，會出現難的工作利潤卻很低。所以我們需要做一個「目前最大利潤」前綴的預處理，計算「從 0 到第 i 的工作為止，能拿到最大的利潤為何。」
    • 這樣預處理完後，我們就能確保，對於每個人，我們都能找到一個「最後一個滿足 difficulty <= ability 的工作」，然後就可以快速得到他能勝任的工作裡面最大的利潤。
  • 二分搜尋：由於 jobs 已經排序過，我可以針對每個人的能力，去二分搜尋去找邊界，我們要找「最後一個滿足 difficulty <= ability 工作的 index」，然後就可以得到 maxProfitAtDifficulty[index]。
  • 雙指針：我們可以把 jobs 和 worker 都排序，當兩個序列都有某種單調性時，我們就可以用雙指針做同步掃描，避免重複拜訪、提升效率。
    • 一邊遍歷 worker，針對每個 worker，我們可以往前掃瞄 jobs 直到 difficulty > ability，
    • 一邊掃描 jobs 的同時，一邊紀錄更新「目前遇過的最大利潤」，這樣我們就可以知道當前 worker 能夠勝任的工作中，最大的利潤是多少。
    • 由於兩邊都排序了，我們可以確保到下一個 worker 時，之前掃描過的 jobs 都不需要回頭看，因為越後面的工人能力只會更強，也就是「過去能做的工作，接下來的人也都一定能做」。
    • 核心精神是：「當兩個序列都排序過後，能夠線性地建立對應關係」，避免每次都從頭比對。

我已經把 jobs 排好，難度從小排到大，那我只要用一個 jobIndex 指針往前掃，遇到符合條件的就更新最大 profit。

假設我們有一個 worker 能力是 5，那只要 jobs 中難度 <= 5 的部分都可以考慮給他做。

接下來下一個工人能力可能是 7，那我就從剛剛停下的 jobIndex 繼續往前掃。
因為他一定也能做能力 5 的工作，需要重頭再掃一次，所以這樣的話，我們就只需要掃一次 jobs，整體時間就是線性的。

Greedy + Binary Search

We can sort the jobs by difficulty, so we can find the last job which difficulty <= ability by binary search for each worker.

difficulty = 1, 2, 3, 4, 5, 6
             O  O  O  X  X  X
             ^^^^^^^ // The job we can assign to gain the maximum profit
                     
worker[i].ability = 3

For the job with difficulty <= ability, how can we find the maximum profit between the jobs within ability efficiently? We can precompute the maximum profit for each difficulty level, that is for jobs with difficulty up to difficulty[i]. For example, precompute[3] = 7 means that the maximum profit for jobs with difficulty <= 3 is 7. This creates a monotonic array of maximum profits.

index       = 0, 1, 2, 3, 4, 5
difficulty  = 1, 2, 3, 4, 5, 6
profit      = 3, 1, 7, 2, 9, 4
precompute  = 3, 3, 7, 7, 9, 9
                       *

// If we select the job with difficulty 3, the maximum profit is 7, max(3, 1, 7, 2) = 7

With the sorted jobs and the precomputed maximum profits, we can find the maximum profit for the worker by binary searching the last job which difficulty <= ability, and find the maximum profit from the precomputed maximum profits during the binary search.

data class Job(
    val difficulty: Int,
    val profit: Int
)

fun maxProfitAssignment(difficulty: IntArray, profit: IntArray, worker: IntArray): Int {
    val n = difficulty.size
    val jobs = Array<Job>(n) {
        Job(difficulty[it], profit[it])
    }
    jobs.sortBy { it.difficulty }

    // Precompute the max profit for jobs with difficulty up to difficulty[i]
    // Or we can just update the profit field for each job without creating a new array.
    val maxProfitAtDifficulty = IntArray(n)
    maxProfitAtDifficulty[0] = jobs.first().profit
    for (i in 1 until n) {
        maxProfitAtDifficulty[i] = maxOf(jobs[i].profit, maxProfitAtDifficulty[i - 1])
    }

    var totalProfit = 0
    for (ability in worker) {
        // Find the last job which difficulty <= ability
        // O O O X X X
        //     ^
        val lastJobIndex = searchJob(jobs, ability)
        if (lastJobIndex >= 0) {
            totalProfit += maxProfitAtDifficulty[lastJobIndex]
        }
    }
    return totalProfit
}

// Find the last position that jobs[i].difficulty <= ability
private fun searchJob(jobs: Array<Job>, ability: Int): Int {
    var left = 0
    var right = jobs.size - 1
    while (left <= right) {
        val middle = left + (right - left) / 2
        val canDo = jobs[middle].difficulty <= ability
        if (canDo) left = middle + 1
        else right = middle - 1
    }
    return right
}
  • Time Complexity: O(n * log n + m * log n), where n is the number of jobs, and m is the number of workers.
  • Space Complexity: O(n).

Greedy + Two Pointers

We can sort the jobs by difficulty, and sort the workers by ability. Then match the job to the worker with the highest profit where the difficulty <= ability of the worker.

After sorting the jobs and workers, both arrays are monotonic, so we can iterate through the jobs and workers via two pointers to find the maximum profit job for each worker. One pointer to iterate through the workers, and another pointer to iterate through the jobs to find the difficulty <= ability of the worker, and find the maximum profit job for the worker during the iteration.

Why Two Pointers?

  • Since jobs are sorted by difficulty, we iterate the job from easy to hard once.
  • As worker ability increases, more jobs

如果把 worker 按照从小到大的顺序排序，那么第 i 个工人能做的工作，他右边的 (worker 值更大的)工人也能做。这意味着，如果我们遍历了所有 difficulty[j] <= worker[i] 的工作，那么从第 i 个工人到第 i+1 个工人，只需要额外遍历 worker[i] < difficulty[j] <= worker[i+1] 的工作。 (Source)

worker =         2,
difficulty  = 1, 2, 3, 5, 6
profit      = 3, 1, 7, 9, 4
                 ^     
                 3 // The maximum from difficulty <= 2    
                 
difficulty  = 1, 2, 3, _, 5, 6
worker      =    2,    4,    6
profit      = 3, 1, 7, _, 9, 4
                 ^ --> ^ --> ^  // The index moves to the right when iterating each worker, it's monotonic.
maxProfit     3  3  7  7  9  9  // max profit job for each worker that can do the job

For the first worker with ability 2, we iterate the job from the beginning to difficulty == 2, and update the maximum profit so far, which is 3. For the second worker with ability 4, we iterate the job from difficulty == 2 to difficulty == 4, and update the maximum profit so far, which is 7. The job pointer is monotonic, so we can find the maximum profit job for each worker efficiently. It's similar to the precomputed maximum profit array in the binary search solution.

fun maxProfitAssignment(difficulty: IntArray, profit: IntArray, worker: IntArray): Int {
    val n = difficulty.size
    val jobs = Array<Job>(n) {
        Job(difficulty[it], profit[it])
    }
    jobs.sortBy { it.difficulty }
    worker.sort()

    var maxProfit = 0
    var totalProfit = 0
    var jobIndex = 0
    for (i in 0 until worker.size) {
        // Iterate through the jobs to find the job with the highest profit that the worker can do, the job is monotonic now.
        // difficulty = 1, 2, 3, 4, ...
        //    workers =          4
        //     profit = 3, 1, 7, 2, ...
        //              3  3  7  7  ...
        while (jobIndex < jobs.size && jobs[jobIndex].difficulty <= worker[i]) {
            maxProfit = maxOf(maxProfit, jobs[jobIndex].profit)
            jobIndex++
        }
        totalProfit += maxProfit
    }
    return totalProfit
}
  • Time Complexity: O(n * log n + m * log m), where n is the number of jobs, and m is the number of workers.
    • Sorting the jobs: O(n * log n).
    • Sorting the workers: O(m * log m).
    • Iterating through the jobs and workers: O(n + m).
  • Space Complexity: O(n).

Pitfalls

  • Not sorting both jobs and workers can lead to inefficient solutions or incorrect matching.
  • Forgetting to update the maximum profit as you iterate through jobs can result in assigning suboptimal jobs to workers.
  • If jobs with higher difficulty have lower profit, not precomputing the maximum profit up to each difficulty can cause mistakes.
  • Be careful with off-by-one errors when advancing pointers, especially when the worker's ability exactly matches a job's difficulty.
  • If there are duplicate difficulties, ensure you always keep the highest profit for each difficulty.