Skip to main content

25. Maximum Number of Tasks You Can Assign

hardAsked at Rappi

Given task strengths, worker strengths, available pills that each boost one worker by a fixed amount, find the max tasks completable — Rappi frames this as the max number of delivery orders matchable to couriers when a fixed pool of surge-credits can boost capacity.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

tasks[i] is the required strength of task i; workers[j] is the strength of worker j. You have pills pills that each increase one worker's strength by strength. Each worker does at most one task. Return the maximum number of tasks you can complete.

Constraints

  • 1 <= n <= 5 * 10^4
  • 0 <= pills <= n
  • 1 <= tasks[i], workers[j], strength <= 10^9

Examples

Example 1

Input
tasks=[3,2,1], workers=[0,3,3], pills=1, strength=1
Output
3

Example 2

Input
tasks=[5,4], workers=[0,0,0], pills=1, strength=5
Output
1

Approaches

1. Try every assignment

Enumerate matchings of tasks to workers, optionally boosting each worker, and keep the best count.

Time
exponential
Space
O(n)
// generate all permutations of worker-to-task assignments + which workers get pills; infeasible for n > 12.

Tradeoff:

2. Binary search on answer + greedy

Sort both arrays; binary-search the answer k. For a candidate k, greedily assign the k hardest tasks to the k strongest workers using a deque — try the strongest worker first; if too weak even with a pill, fail. Otherwise prefer to skip the pill when possible.

Time
O((n + m) log^2 n)
Space
O(n)
// Sketch:
function maxTaskAssign(tasks, workers, pills, strength) {
  tasks.sort((a,b)=>a-b); workers.sort((a,b)=>a-b);
  const can = (k) => {
    const dq = workers.slice(workers.length - k);
    let p = pills;
    for (let i = k - 1; i >= 0; i--) {
      if (dq.length && dq[dq.length-1] >= tasks[i]) { dq.pop(); continue; }
      if (p > 0 && dq[0] + strength >= tasks[i]) { dq.shift(); p--; continue; }
      return false;
    }
    return true;
  };
  let lo = 0, hi = Math.min(tasks.length, workers.length);
  while (lo < hi) { const mid = (lo + hi + 1) >> 1; can(mid) ? lo = mid : hi = mid - 1; }
  return lo;
}

Tradeoff:

Rappi-specific tips

Rappi singles out 'binary search on the answer' as the litmus test for this problem — they'll openly tell you greedy alone fails and want you to derive the BS-feasibility monotone property out loud.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Maximum Number of Tasks You Can Assign and other Rappi interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →