algo-greedy-01

# Freelance gig scheduling for maximum payout

You are a freelancer planning your calendar. There is a queue of one-day gigs
on offer. Each gig `i` has:

- a **deadline** `d_i` (a positive integer) — the gig is only worth anything if
  you complete it on or before day `d_i`, and
- a **payout** `p_i` (a non-negative integer) — what you earn if you complete it
  in time.

Days are numbered `1, 2, 3, ...`. Every gig takes **exactly one full day**, and
you can work on **at most one gig per day**. You may accept any subset of the
gigs and choose which day to do each accepted gig, as long as no two accepted
gigs share a day and each accepted gig is done on some day `<= its deadline`.
Gigs you don't accept earn nothing.

Implement a file **`solution.py`** containing:

```python
def max_payout(gigs: list[tuple[int, int]]) -> int:
    """Return the maximum total payout achievable.

    `gigs` is a list of (deadline, payout) pairs. Return an int.
    """
```

## What to return

Return the **maximum total payout** you can earn with a valid schedule. You do
**not** need to return the schedule itself — only the best achievable total.

## Why this is subtle

A tempting greedy — "sort gigs by payout, and place each accepted gig on the
earliest free day within its deadline" — is **wrong**. Consider two gigs:

- gig A: deadline 2, payout 100
- gig B: deadline 1, payout 50

The correct answer is **150**: do A on day 2 and B on day 1. But if you place
the higher-payout gig A on the *earliest* free day (day 1), you occupy the only
day B could ever use, and you're stuck with just 100. The fix is an
exchange-argument insight: when you accept a gig, reserve it as **late** as its
deadline allows, keeping earlier days open for gigs with tighter deadlines.
Likewise, sorting purely by deadline (or accepting gigs first-come) can force
you to keep a cheap gig over a strictly better one competing for the same day.

## Constraints

- `0 <= len(gigs)`; large instances (up to `2 * 10^5` gigs) are tested, so an
  `O(n^2)` day-by-day scan will be too slow — aim for roughly `O(n log n)`.
- `1 <= d_i` and `0 <= p_i`, each up to about `10^9`. Deadlines may be far
  larger than the number of gigs.
- The empty gig list returns `0`.

## Examples

```python
assert max_payout([]) == 0
assert max_payout([(1, 42)]) == 42
assert max_payout([(2, 100), (1, 50)]) == 150          # place the rich gig late
assert max_payout([(1, 1), (1, 100)]) == 100           # one day-1 slot, keep 100
assert max_payout([(2, 100), (1, 19), (2, 27), (1, 25), (3, 15)]) == 142
assert max_payout([(1000, 5), (1000, 6), (1000, 7)]) == 18  # all fit
```

import heapq
import itertools
import random

from solution import max_payout


# ----------------------------------------------------------------------------
# Independent oracles used to check the solution on random / large inputs.
# ----------------------------------------------------------------------------

def heap_oracle(gigs):
    """Classic min-heap greedy for job sequencing with deadlines.

    Process gigs in increasing deadline order, keep a min-heap of accepted
    payouts, and whenever more gigs are accepted than the current deadline
    allows, drop the smallest-payout accepted gig. The heap's sum is optimal.
    This is a different implementation from the reference (which uses a
    disjoint-set over day-slots), so agreement is a strong correctness signal.
    """
    heap = []
    for d, p in sorted(gigs, key=lambda x: x[0]):
        heapq.heappush(heap, p)
        if len(heap) > d:
            heapq.heappop(heap)
    return sum(heap)


def brute_force(gigs):
    """Exhaustive optimum for tiny inputs.

    Try every subset of gigs; a subset is schedulable iff we can match each
    gig to a distinct day <= its deadline (checked by the standard earliest
    -deadline-first feasibility greedy). Only feasible for very small n.
    """
    n = len(gigs)
    best = 0
    for r in range(n + 1):
        for subset in itertools.combinations(range(n), r):
            chosen = sorted(subset, key=lambda i: gigs[i][0])
            day = 0
            ok = True
            for i in chosen:
                day += 1
                if day > gigs[i][0]:
                    ok = False
                    break
            if ok:
                best = max(best, sum(gigs[i][1] for i in subset))
    return best


# ----------------------------------------------------------------------------
# Hand-verified small cases.
# ----------------------------------------------------------------------------

def test_empty():
    assert max_payout([]) == 0


def test_single_gig_within_deadline():
    assert max_payout([(1, 42)]) == 42
    assert max_payout([(5, 7)]) == 7


def test_two_gigs_no_conflict():
    assert max_payout([(1, 10), (2, 20)]) == 30


def test_latest_slot_subtlety():
    # The exchange-argument crux: the high-payout gig has the LATER deadline.
    # Placing it at its latest feasible day (day 2) leaves day 1 free for the
    # tight-deadline gig, yielding 150. A greedy that places the high-payout
    # gig at the EARLIEST free day (day 1) blocks the other gig -> only 100.
    assert max_payout([(2, 100), (1, 50)]) == 150


def test_must_prefer_higher_payout_on_tie_deadline():
    assert max_payout([(1, 1), (1, 100)]) == 100
    assert max_payout([(1, 100), (1, 1)]) == 100


def test_classic_five_gig_instance():
    gigs = [(2, 100), (1, 19), (2, 27), (1, 25), (3, 15)]
    assert max_payout(gigs) == 142


def test_four_gig_instance():
    assert max_payout([(1, 10), (2, 10), (2, 15), (1, 20)]) == 35


def test_all_same_deadline_one():
    assert max_payout([(1, 3), (1, 9), (1, 4), (1, 2)]) == 9


def test_deadlines_far_beyond_count():
    assert max_payout([(1000, 5), (1000, 6), (1000, 7)]) == 18


def test_greedy_by_deadline_alone_is_wrong():
    gigs = [(1, 5), (2, 6), (2, 7), (3, 4), (1, 20), (3, 3)]
    assert max_payout(gigs) == brute_force(gigs)


def test_zero_payout_gigs_are_never_harmful():
    assert max_payout([(1, 0), (1, 0)]) == 0
    assert max_payout([(2, 0), (1, 5)]) == 5


# ----------------------------------------------------------------------------
# Randomized cross-checks against brute force (small) and heap oracle.
# ----------------------------------------------------------------------------

def test_random_small_vs_bruteforce():
    rng = random.Random(1234)
    for _ in range(400):
        n = rng.randint(0, 7)
        gigs = [(rng.randint(1, 6), rng.randint(0, 50)) for _ in range(n)]
        assert max_payout(gigs) == brute_force(gigs)


def test_random_medium_vs_heap_oracle():
    rng = random.Random(99)
    for _ in range(60):
        n = rng.randint(1, 500)
        gigs = [(rng.randint(1, n + 5), rng.randint(1, 10**6)) for _ in range(n)]
        assert max_payout(gigs) == heap_oracle(gigs)


def test_random_tight_deadlines_vs_heap_oracle():
    rng = random.Random(7)
    for _ in range(60):
        n = rng.randint(1, 400)
        maxd = rng.randint(1, 5)
        gigs = [(rng.randint(1, maxd), rng.randint(1, 1000)) for _ in range(n)]
        assert max_payout(gigs) == heap_oracle(gigs)


def test_large_input_performance_and_correctness():
    # Big instance: an O(n^2) slot scan would blow the time budget, and a
    # naive greedy would give a wrong total. Must match the heap oracle.
    rng = random.Random(2024)
    n = 200_000
    gigs = [(rng.randint(1, 10**9), rng.randint(1, 10**9)) for _ in range(n)]
    assert max_payout(gigs) == heap_oracle(gigs)


def test_large_tight_deadlines():
    rng = random.Random(555)
    n = 200_000
    gigs = [(rng.randint(1, 50), rng.randint(1, 10**9)) for _ in range(n)]
    assert max_payout(gigs) == heap_oracle(gigs)

You are an expert programmer. Solve the task exactly as specified. Output your solution as fenced code blocks using the required file name(s) and the exact function/type signatures requested. Prefer correctness; do not include prose outside code unless asked.

```python
import heapq

def max_payout(gigs: list[tuple[int, int]]) -> int:
    """Return the maximum total payout achievable.

    `gigs` is a list of (deadline, payout) pairs. Return an int.
    """
    # Sort gigs by deadline in ascending order.
    # This allows us to process gigs and ensure that at any point,
    # the number of selected gigs does not exceed the current deadline.
    gigs.sort(key=lambda x: x[0])
    
    # Min-heap to store the payouts of the currently selected gigs.
    # We use a min-heap to efficiently remove the gig with the smallest payout
    # if we exceed the capacity allowed by the deadlines.
    min_heap = []
    
    for deadline, payout in gigs:
        # Tentatively accept the gig
        heapq.heappush(min_heap, payout)
        
        # If the number of accepted gigs exceeds the current deadline,
        # it means we have more gigs than available days (1 to deadline).
        # We must reject one gig. To maximize total payout, we reject
        # the one with the smallest payout.
        if len(min_heap) > deadline:
            heapq.heappop(min_heap)
            
    # The sum of payouts in the heap is the maximum achievable payout.
    return sum(min_heap)
```

The problem asks us to select a subset of gigs and schedule them on distinct days such that each selected gig $i$ is scheduled on a day $t \le d_i$, maximizing the sum of payouts. Each gig takes 1 day.

Let $n$ be the number of gigs.
Constraints: $n \le 2 \cdot 10^5$, deadlines and payouts up to $10^9$.
Time complexity requirement: roughly $O(n \log n)$.

Let's analyze the properties of the optimal solution.
This is a classic problem often solved using a greedy approach with a priority queue or a disjoint set union (DSU) structure.

Approach 1: Greedy with Priority Queue (Min-Heap)
Sort the gigs by deadline in ascending order.
Iterate through the sorted gigs.
Maintain a min-heap of payouts of the gigs currently selected.
For each gig $(d, p)$:
1. Add $p$ to the heap.
2. If the size of the heap exceeds the current deadline $d$, it means we have selected more gigs than there are available days up to day $d$. Since we process gigs in increasing order of deadlines, all gigs currently in the heap have deadlines $\le d$. Thus, we can schedule at most $d$ gigs among them. To maximize payout, we should remove the gig with the smallest payout from our selection.
3. Pop the smallest element from the heap.

Why does this work?
Suppose we are at step $i$ considering gig $i$ with deadline $d_i$. We have processed all gigs with deadline $\le d_i$. Let $S$ be the set of selected gigs so far. All gigs in $S$ have deadlines $\le d_i$. The number of available days for these gigs is $d_i$. If $|S| > d_i$, we must discard at least one gig. Discarding the one with the minimum payout is locally optimal. Does it hurt future decisions?
Future gigs have deadlines $d_j \ge d_i$. If we keep a set of size $d_i$ with maximum total payout for the current constraint, we leave "room" for future gigs. Specifically, having fewer gigs selected (size $\le d_i$) is always better or equal to having more gigs selected (size $> d_i$) because it satisfies the capacity constraint for day $d_i$ and any future day $d_j \ge d_i$ will have capacity $d_j \ge d_i$. Wait, this logic is slightly flawed. The constraint is not just "total count $\le$ deadline". It's about specific days.
However, a known theorem for this problem states that if we have a set of jobs with deadlines, they can be scheduled if and only if for every $k$, the number of jobs with deadline $\le k$ is at most $k$.
By maintaining the invariant that for the current deadline $d$, the number of selected jobs with deadline $\le d$ is at most $d$, and maximizing the sum of payouts, we are good.
Actually, the condition is slightly more subtle. The condition "for every $k$, count of jobs with deadline $\le k$ is $\le k$" is necessary and sufficient for schedulability.
Let's trace the algorithm again.
Sort gigs by deadline: $(d_1, p_1), (d_2, p_2), \dots, (d_n, p_n)$ where $d_1 \le d_2 \le \dots \le d_n$.
Heap stores payouts of selected gigs.
For each gig $(d, p)$:
  Push $p$ to heap.
  If heap size $> d$:
    Pop min from heap.
At the end, sum of heap elements is the answer.

Let's check the constraint logic.
Suppose after processing all gigs with deadline $\le X$, the heap contains a set of gigs $H_X$.
The algorithm ensures $|H_X| \le X$ because whenever we process a gig with deadline $d$, if size becomes $d+1$, we pop one. Since deadlines are non-decreasing, for any $d' < d$, the size constraint $|H_{d'}| \le d'$ was already enforced.
Is it true that $|H_X| \le X$ for all $X$?
Yes. When we are at gig with deadline $d$, we ensure size $\le d$. For any $X < d$, the size of the heap was checked against $X$ when we processed the last gig with deadline $X$ (or earlier). Since we only add elements and remove elements, and we only remove when size exceeds current deadline, the size never exceeds the current deadline. Wait.
Example:
Gigs: (1, 10), (2, 20), (2, 30).
Sorted: (1, 10), (2, 20), (2, 30).
1. Process (1, 10). Heap: [10]. Size 1. $1 \le 1$. OK.
2. Process (2, 20). Heap: [10, 20]. Size 2. $2 \le 2$. OK.
3. Process (2, 30). Heap: [10, 20, 30]. Size 3. $3 > 2$. Pop min (10). Heap: [20, 30]. Size 2.
Final sum: 50.
Is this valid?
Selected: (2, 20), (2, 30).
Deadlines: 2, 2.
Days available: 1, 2.
Can we schedule? Yes. Day 1: (2, 20), Day 2: (2, 30). Or vice versa.
Wait, the condition "count of jobs with deadline $\le k$ is $\le k$" is necessary.
Here for $k=1$, jobs with deadline $\le 1$ is empty set (since we removed (1, 10)). Count 0 $\le 1$.
For $k=2$, jobs with deadline $\le 2$ are {(2, 20), (2, 30)}. Count 2 $\le 2$.
So it works.

Let's check the example from the prompt.
Gigs: [(2, 100), (1, 50)]
Sorted by deadline: [(1, 50), (2, 100)]
1. Process (1, 50). Heap: [50]. Size 1 $\le 1$.
2. Process (2, 100). Heap: [50, 100]. Size 2 $\le 2$.
Sum: 150. Correct.

Example: [(1, 1), (1, 100)]
Sorted: [(1, 1), (1, 100)] (order doesn't matter for same deadline)
1. Process (1, 1). Heap: [1]. Size 1 $\le 1$.
2. Process (1, 100). Heap: [1, 100]. Size 2 > 1. Pop 1. Heap: [100].
Sum: 100. Correct.

Example: [(2, 100), (1, 19), (2, 27), (1, 25), (3, 15)]
Sorted by deadline:
(1, 19), (1, 25), (2, 100), (2, 27), (3, 15)
1. (1, 19): Heap [19], size 1 $\le 1$.
2. (1, 25): Heap [19, 25], size 2 > 1. Pop 19. Heap [25].
3. (2, 100): Heap [25, 100], size 2 $\le 2$.
4. (2, 27): Heap [25, 100, 27], size 3 > 2. Pop 25. Heap [27, 100].
5. (3, 15): Heap [27, 100, 15], size 3 $\le 3$.
Sum: 27 + 100 + 15 = 142. Correct.

Example: [(1000, 5), (1000, 6), (1000, 7)]
Sorted: same.
1. (1000, 5): Heap [5], size 1 $\le 1000$.
2. (1000, 6): Heap [5, 6], size 2 $\le 1000$.
3. (1000, 7): Heap [5, 6, 7], size 3 $\le 1000$.
Sum: 18. Correct.

Complexity:
Sorting: $O(n \log n)$.
Loop: $n$ iterations.
Heap operations: push and pop are $O(\log n)$.
Total: $O(n \log n)$.
Space: $O(n)$ for heap.
This fits the constraints.

Approach 2: Greedy with Priority Queue (Max-Heap) - "Reverse" approach
Sort gigs by deadline in descending order.
Iterate through gigs.
Maintain a max-heap of payouts of gigs considered so far.
Keep track of current day `t`. Initially `t` is the deadline of the first gig (largest deadline).
Actually, a simpler version of this logic:
Sort gigs 
…[35252 chars elided]…
, int]]` syntax is valid in Python 3.9+.
   If the environment is older (e.g. 3.8), it might need `from typing import List, Tuple`.
   However, modern coding challenges usually support 3.9+.
   The prompt uses `list[tuple[int, int]]` in the signature, so I assume it's supported.
   I'll stick to the prompt's signature.

   Wait, is `gigs` guaranteed to be a list of tuples?
   Yes.
   
   Is it possible `gigs` is `None`?
   Constraints say `0 <= len(gigs)`, implies it's a list.
   
   Okay, ready.

   One last thought: Is there any scenario where `len(min_heap) > deadline` is not the correct check?
   Suppose we have gigs with deadlines 2, 2, 2.
   Sorted: (2, p1), (2, p2), (2, p3).
   1. Push p1. Size 1 <= 2.
   2. Push p2. Size 2 <= 2.
   3. Push p3. Size 3 > 2. Pop min. Size 2.
   Correct.
   
   Suppose deadlines 1, 2, 3.
   1. (1, p1). Size 1 <= 1.
   2. (2, p2). Size 2 <= 2.
   3. (3, p3). Size 3 <= 3.
   Correct.
   
   Suppose deadlines 1, 1, 3.
   1. (1, p1). Size 1 <= 1.
   2. (1, p2). Size 2 > 1. Pop min. Size 1.
   3. (3, p3). Size 2 <= 3.
   Correct.
   
   The logic holds because the constraint is cumulative.
   At step $i$ with deadline $d_i$, we have selected a set of jobs $S_i$.
   All jobs in $S_i$ have deadline $\le d_i$.
   The condition for schedulability of $S_i$ is that for all $t$, count of jobs in $S_i$ with deadline $\le t$ is $\le t$.
   Since all jobs in $S_i$ have deadline $\le d_i$, for any $t \ge d_i$, the count is $|S_i|$.
   So we need $|S_i| \le t$ for all $t \ge d_i$.
   The tightest constraint is $t = d_i$, so $|S_i| \le d_i$.
   For $t < d_i$, the count is the number of jobs in $S_i$ with deadline $\le t$.
   Since we processed jobs in increasing order of deadlines, when we were at the last job with deadline $t$ (or earlier), we ensured the count was $\le t$.
   Adding a job with deadline $d_i > t$ does not increase the count for deadline $\le t$.
   So the constraints for $t < d_i$ remain satisfied.
   Thus, checking $|S_i| \le d_i$ is sufficient.

   The solution is correct.