Maximize optional tasks under daily limit
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
You are given an integer limit and two integer arrays required and optional of length n. For each day i, you must schedule required[i]. If time remains on that day (not exceeding limit), you may schedule at most one optional task; each optional task can be used at most once and can be assigned to any day. Goal: maximize the number of optional tasks scheduled across n days without exceeding the daily limit.
Return:
(
1) the maximum count of scheduled optional tasks, and
(
2) one valid assignment of optional tasks to days (or indicate none for a day).
Example:
limit = 7
required = [4, 5, 2, 4]
optional = [5, 6, 3, 4]
One optimal plan schedules 2 optional tasks.
Answer the following:
- Describe an efficient algorithm, prove why it is correct, and analyze time and space complexity.
- Implement the algorithm in the language of your choice.
- How would your approach change if each optional task were tied to a specific day (i.e., optional[i] can only be used on day i)?
- How would you handle cases where some required[i] > limit?
- How would you generalize if up to k optional tasks could be scheduled per day?
Quick Answer: This question evaluates algorithmic problem-solving in scheduling and combinatorial optimization, assessing understanding of capacity-constrained assignment, greedy or matching strategies, and correctness and complexity reasoning.
You are given an integer `limit` and two integer arrays `required` and `optional` of length `n`.
For each day `i` you must schedule `required[i]`. If time remains on that day without exceeding `limit`, you may schedule **at most one** optional task. Each optional task can be used **at most once** and may be assigned to **any** day.
Return a tuple `(count, assignment)`:
1. `count` — the maximum number of optional tasks that can be scheduled across all `n` days, and
2. `assignment` — a list of length `n` where `assignment[i]` is the **cost of the optional task** placed on day `i`, or `-1` if no optional task is placed on that day. Any one valid optimal assignment is accepted; this reference produces the deterministic plan that, processing days in ascending order of free slack, gives each day the cheapest still-unused optional task that fits.
A day `i` has free slack `limit - required[i]`. An optional task of cost `o` fits on day `i` only if `o <= limit - required[i]` (so days where `required[i] >= limit` can hold no optional task).
**Example**
```
limit = 7
required = [4, 5, 2, 4]
optional = [5, 6, 3, 4]
=> (2, [3, -1, 4, -1])
```
Day 0 (slack 3) takes optional 3; day 2 (slack 5) takes optional 4. Days 1 and 4 have no room for any remaining optional, so 2 optional tasks is optimal.
Constraints
- 1 <= n <= 10^5 (n may be 0 if both arrays are empty)
- 1 <= limit <= 10^9
- 0 <= required[i], optional[i] <= 10^9
- len(required) == len(optional) == n
- If required[i] >= limit, day i cannot hold any optional task
Examples
Input: (7, [4, 5, 2, 4], [5, 6, 3, 4])
Expected Output: (2, [3, -1, 4, -1])
Explanation: Prompt example. Slacks: day0=3, day1=2, day2=5, day3=3. Processing tightest-first, day1(2) fits nothing unused that helps, day0(3) takes optional 3, day3(3) finds no remaining fit, day2(5) takes optional 4. Max = 2.
Input: (7, [7, 7, 7], [1, 2, 3])
Expected Output: (0, [-1, -1, -1])
Explanation: Every day's required equals limit, so slack is 0 everywhere and no optional task fits.
Hints
- Each day independently offers `limit - required[i]` units of free slack; an optional task only fits if its cost is <= that slack. The day's required cost is fixed and unavoidable.
- This reduces to a bipartite matching: optional task fits day iff cost <= slack. Because both sides are one-dimensional thresholds, sorting beats general matching.
- Sort the day slacks ascending and the optional costs ascending. Walk the days from tightest to loosest and assign each the cheapest still-unused optional that fits — an exchange argument shows this never reduces the achievable count.
- Follow-up — optional[i] tied to day i: it becomes n independent yes/no checks (`optional[i] <= limit - required[i]`); no sorting or matching needed.
- Follow-up — required[i] > limit: that day is infeasible for its own required task; either report it as impossible or treat its optional slack as 0 (it can hold nothing). Follow-up — up to k optional per day: give each day k slots and run the same sorted-greedy, filling the smallest fitting optional tasks into the tightest available slots.