Maximize optional tasks under daily limit

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?

Maximize Optional Tasks Under Daily Limit

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

Hints

1. 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.
2. This reduces to a bipartite matching: optional task fits day iff cost <= slack. Because both sides are one-dimensional thresholds, sorting beats general matching.
3. 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.
4. 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.
5. 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.