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.
    """
    if not gigs:
        return 0
        
    # Sort gigs by deadline ascending.
    # Processing in deadline order allows us to maintain a valid schedule
    # incrementally, knowing that all currently selected gigs can fit 
    # within days 1..current_deadline.
    gigs.sort(key=lambda x: x[0])
    
    # Min-heap to keep track of the payouts of selected gigs.
    # We maintain the invariant that len(min_heap) <= current_deadline.
    min_heap = []
    
    for d, p in gigs:
        if len(min_heap) < d:
            # There is at least one free day <= d available.
            # We greedily accept this gig.
            heapq.heappush(min_heap, p)
        elif p > min_heap[0]:
            # All days <= d are occupied by previously accepted gigs,
            # but this gig pays more than the least profitable one we've kept.
            # Replace the smallest payout to increase total earnings.
            heapq.heapreplace(min_heap, p)
            
    return sum(min_heap)
```

The problem asks us to select a subset of gigs and assign each selected gig to a distinct day $t \le d_i$ such that the total payout is maximized. Each gig takes one day.

This is a classic problem known as "Job Sequencing with Deadlines" or "Scheduling to Minimize Lateness" (though here we maximize profit, not minimize lateness).
The standard greedy approach for maximizing profit is:
1. Sort the gigs in descending order of payout.
2. Iterate through the sorted gigs. For each gig, try to schedule it as late as possible before its deadline. If we can find a free day $t \le d_i$, we schedule it there and add its payout to the total.

Wait, the prompt says: "A tempting greedy — 'sort gigs by payout, and place each accepted gig on the earliest free day within its deadline' — is wrong."
It suggests placing it as *late* as possible. Let's verify if sorting by payout descending and placing as late as possible is correct.
Actually, the standard algorithm for this problem is indeed: sort by profit descending, then for each job, find the latest available time slot $\le$ deadline. This can be implemented efficiently using a Disjoint Set Union (DSU) or a max-heap.
Wait, another approach is to process gigs in increasing order of deadlines, and maintain a min-heap of selected payouts. If the current gig's payout is greater than the smallest payout in the heap, or if the heap size is less than the current deadline (actually, less than the number of available slots up to current deadline), we add it.
Let's analyze the min-heap approach:
Sort gigs by deadline ascending.
Iterate through gigs. Maintain a min-heap of payouts of selected gigs.
For each gig $(d, p)$:
  If current heap size $< d$, we can potentially add this gig. Push $p$ to heap.
  Else (heap size $\ge d$), it means we have already selected $d$ gigs that all have deadlines $\le d$ (since we process in deadline order). Actually, the condition is slightly different. The number of available days up to deadline $d$ is $d$. If we have already selected $d$ gigs, we cannot add another one without dropping one. So we compare $p$ with the minimum payout in the heap. If $p > \min(\text{heap})$, we pop the min and push $p$. Otherwise, we discard the current gig.
This approach works and runs in $O(n \log n)$ time.
Let's trace it carefully.
Suppose gigs are sorted by deadline: $(d_1, p_1), (d_2, p_2), \dots$ with $d_1 \le d_2 \le \dots$.
We maintain a min-heap `selected` of payouts.
For each $(d, p)$:
  If `len(selected) < d`:
    `heapq.heappush(selected, p)`
  Else:
    # We have `d` gigs already selected. Since we process by deadline, all selected gigs have deadline $\le d$.
    # Actually, the number of available slots up to day $d$ is exactly $d$.
    # If `len(selected) == d`, we are full up to day $d$. We can only add this gig if it replaces a lower payout gig.
    if `p > selected[0]`:
      `heapq.heapreplace(selected, p)`
    # else ignore
This is a well-known algorithm for this problem. It's correct and efficient.
Complexity: Sorting takes $O(n \log n)$. Heap operations take $O(\log n)$ per gig. Total $O(n \log n)$.
Constraints: $n \le 2 \cdot 10^5$, $d_i, p_i \le 10^9$. The heap approach handles large $d_i$ naturally because we only care about `len(selected)`, which is at most $n$. We don't allocate an array of size $d_i$.

Let's test the examples with this algorithm.
Example 1: `[]` -> heap empty, returns 0. Correct.
Example 2: `[(1, 42)]` -> sorted: same. len=0 < 1, push 42. heap=[42]. sum=42. Correct.
Example 3: `[(2, 100), (1, 50)]` -> sorted by deadline: `[(1, 50), (2, 100)]`.
  - (1, 50): len=0 < 1, push 50. heap=[50].
  - (2, 100): len=1 < 2, push 100. heap=[50, 100].
  sum = 150. Correct.
Example 4: `[(1, 1), (1, 100)]` -> sorted: `[(1, 1), (1, 100)]` (stable sort or arbitrary order for same deadline).
  - (1, 1): len=0 < 1, push 1. heap=[1].
  - (1, 100): len=1 is not < 1. Check 100 > 1? Yes. replace. heap=[100].
  sum = 100. Correct.
Example 5: `[(2, 100), (1, 19), (2, 27), (1, 25), (3, 15)]`
  Sort by deadline:
  (1, 19), (1, 25), (2, 100), (2, 27), (3, 15)  [order of same deadline doesn't strictly matter for correctness, but let's assume stable or arbitrary]
  Let's process:
  1. (1, 19): len=0 < 1 -> push 19. heap=[19]
  2. (1, 25): len=1 not < 1. 25 > 19? Yes -> replace. heap=[25]
  3. (2, 100): len=1 < 2 -> push 100. heap=[25, 100]
  4. (2, 27): len=2 not < 2. 27 > 25? Yes -> replace. heap=[27, 100]
  5. (3, 15): len=2 < 3 -> push 15. heap=[15, 27, 100]
  Sum = 15+27+100 = 142. Correct.
Example 6: `[(1000, 5), (1000, 6), (1000, 7)]`
  Sort: same.
  1. (1000, 5): len=0 < 1000 -> push 5. heap=[5]
  2. (1000, 6): len=1 < 1000 -> push 6. heap=[5, 6]
  3. (1000, 7): len=2 < 1000 -> push 7. heap=[5, 6, 7]
  Sum = 18. Correct.

The algorithm seems solid.

Wait, is there any edge case where `len(selected) < d` condition is insufficient?
The condition `len(selected) < d` means we have selected fewer than `d` gigs so far. Since all selected gigs have deadlines $\le d$ (because we process in deadline order), they can all be scheduled in days $1 \dots d$. Actually, they can be scheduled in days $1 \dots \text{len(selected)}$. Since $\text{len(selected)} < d$, there is at least one free day $\le d$ available for the current gig. So we can always add it.
If `len(selected) == d`, it means we have already selected $d$ gigs, all with deadlines $\le d$. By Hall's Marriage Theorem or a simple greedy argument, these $d$ gigs can be scheduled in days $1 \dots d$. There are no free days $\le d$. So we can only add the current gig by replacing the one with the smallest payout.
This logic holds.

One minor point: sorting by deadline ascending. If deadlines are equal, does the order matter?
Suppose we have (2, 10) and (2, 20).
If we process (2, 10) first: len=0 < 2 -> push 10. heap=[10].
Then (2, 20): len=1 < 2 -> push 20. heap=[10, 20]. Sum=30.
If we process (2, 20) first: len=0 < 2 -> push 20. heap=[20].
Then (2, 10): len=1 < 2 -> push 10. heap=[10, 20]. Sum=30.
Order doesn't matter for same deadline because we just fill up to capacity $d$. The heap will contain the largest payouts among thos
…[11949 chars elided]…
 if `d` is very large, say $10^9$, and we have $N=10^5$ gigs? `len(min_heap)` will be at most $10^5$, which is $< 10^9$. So we push all. Correct.
What if `gigs` has negative payouts? Constraints say `0 <= p_i`. So non-negative.
All constraints satisfied.
Code is optimal.
Final answer generation. 
```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.
    """
    if not gigs:
        return 0
        
    # Sort gigs by deadline ascending.
    gigs.sort(key=lambda x: x[0])
    
    # Min-heap to keep track of the payouts of selected gigs.
    min_heap = []
    
    for d, p in gigs:
        if len(min_heap) < d:
            # There is at least one free day <= d available.
            heapq.heappush(min_heap, p)
        elif p > min_heap[0]:
            # All days <= d are occupied, but this gig pays more than 
            # the least profitable one we've accepted. Swap them.
            heapq.heapreplace(min_heap, p)
            
    return sum(min_heap)
```
This looks perfect. I will output it. 
One minor point: `gigs.sort(key=lambda x: x[0])` modifies the input list. Usually acceptable in competitive programming / algorithm tasks unless specified otherwise. If immutability is required, we could sort a copy, but it's not specified. I'll assume in-place sort is fine. To be safe, I can just use `sorted_gigs = sorted(gigs, key=lambda x: x[0])` but it uses extra memory. Given constraints, in-place is fine. I'll stick with in-place or just `gigs.sort()`. It's standard.
I'll output the code as is.
Done. 
Proceeds. 
[Output Generation] -> matches the final code block. 
All steps verified. 
Final Check of the prompt: "Implement a file solution.py containing: ..."
I will provide exactly that.
No extra text.
Done. 
(Self-Correction/Refinement during generation prep)
Actually, `gigs.sort(key=lambda x: x[0])` is fine.
I'll produce the solution. 
All good. 
Output matches response. 
[Done]