Select maximum tasks before deadlines

You are given a set of tasks, each with a positive duration and a deadline (lastDay). You may schedule tasks in any order but only one at a time. Find the maximum number of tasks you can complete such that each chosen task finishes by its deadline. Return the count and describe an O(n log n) algorithm and its correctness intuition.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Select Maximum Tasks Before Deadlines

You are given a list of tasks, where each task is a pair [duration, lastDay]: duration is the positive number of time units the task takes, and lastDay is the deadline by which the task must be finished (the task must complete at or before this absolute time). You process tasks sequentially on a single machine starting at time 0 — only one task runs at a time, and you may schedule the chosen tasks in any order. A task counts as completed only if its finish time is <= lastDay.

Return the maximum number of tasks you can complete on time.

Describe an O(n log n) algorithm. Hint: sort by deadline and use a max-heap to greedily evict the longest task whenever the running schedule overruns the current deadline.

Constraints

• 1 <= tasks.length <= 10^4 (the list may also be empty, in which case the answer is 0)
• tasks[i].length == 2
• 1 <= duration <= 10^4
• 1 <= lastDay <= 10^9
• Time starts at 0; a chosen task with cumulative finish time t is valid only if t <= lastDay

Examples

Example 1

Input: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
Output: 3

Explanation: Take durations 100, 200, 1000 (skip 2000). Finishing in deadline order: 100 (<=200), 300 (<=1250 for the 1000-task? compute via greedy) — the greedy keeps 3 tasks; the 2000-duration task is evicted as the longest when the schedule overruns.

Example 2

Input: [[1, 2], [2, 4], [3, 6]]
Output: 3

Explanation: All three fit: cumulative finish times 1<=2, 3<=4, 6<=6.

Hints

1. Process candidate tasks in non-decreasing order of deadline. Intuitively, to keep more tasks you should respect the earliest deadlines first.
2. Keep a running sum of durations of the tasks you have committed to. When that sum exceeds the current task's deadline, you have over-committed and must drop exactly one task.
3. Drop the task with the largest duration committed so far (a max-heap gives it in O(log n)). Removing the longest one frees the most time while keeping the count change neutral — you replace it with the shorter current task only if that helps.
4. Correctness intuition: sorting by deadline means every task still in the heap fits under all later deadlines too; evicting the longest keeps the chosen set both feasible and maximal in count at each step (an exchange argument).

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

You are given a set of tasks, each with a positive duration and a deadline (lastDay). You may schedule tasks in any order but only one at a time. Find the maximum number of tasks you can complete such that each chosen task finishes by its deadline. Return the count and describe an O(n log n) algorithm and its correctness intuition.

Recommended Approach

Start with a brute-force baseline to confirm correctness, then identify the repeated work or ordering property that enables a better data structure such as a hash map, heap, stack, queue, two pointers, prefix sums, BFS/DFS, or dynamic programming. Write the implementation around a small invariant and test that invariant directly.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

State the baseline complexity and the optimized complexity. For most interview constraints, justify why the optimized approach meets the expected input size.

Edge Cases and Tests

Empty and singleton inputs, duplicates, ties, invalid inputs, boundary values, and tests that exercise the main invariant.