Greedy Algorithms

#Topic: Activity Selection Problem (Meeting Room Assignment) — Greedy
# Time: O(n log n)   Space: O(n)


def activity_selection(activities: list[tuple[int, int]]) -> list[tuple[int, int]]:
    """Select the maximum number of activities (so that they do not overlap).

    Key: Sort in ascending order based on end time
    → Select activities that end earlier first

    Time: O(n log n) — sorting dominates
    Space: O(n)"""
    #Sort by end time
    sorted_activities = sorted(activities, key=lambda x: (x[1], x[0]))

    selected: list[tuple[int, int]] = []
    last_end = -1   #End time of the last selected activity

    for start, end in sorted_activities:
        if start >= last_end:   #No overlap
            selected.append((start, end))
            last_end = end

    return selected


def activity_selection_with_idx(
    activities: list[tuple[int, int]]
) -> tuple[int, list[int]]:
    """Return the maximum number of activities + the indices selected.

    Time: O(n log n)
    Space: O(n)"""
    indexed = sorted(enumerate(activities), key=lambda x: x[1][1])
    selected_idx: list[int] = []
    last_end = -1

    for idx, (start, end) in indexed:
        if start >= last_end:
            selected_idx.append(idx)
            last_end = end

    return len(selected_idx), selected_idx


def max_non_overlapping(intervals: list[tuple[int, int]]) -> int:
    """LeetCode style: Maximum number of non-overlapping intervals.

    Time: O(n log n)
    Space: O(1)"""
    sorted_intervals = sorted(intervals, key=lambda x: x[1])
    count = 0
    last_end = float("-inf")

    for start, end in sorted_intervals:
        if start >= last_end:
            count += 1
            last_end = end

    return count


def min_removals_for_non_overlap(intervals: list[tuple[int, int]]) -> int:
    """How many should be removed to avoid overlaps?

    Time: O(n log n)
    Space: O(1)"""
    total = len(intervals)
    keep = max_non_overlapping(intervals)
    return total - keep


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    #Baekjoon 1931 type data
    activities = [
        (1, 4), (3, 5), (0, 6), (5, 7),
        (3, 9), (5, 9), (6, 10), (8, 11),
        (8, 12), (2, 14), (12, 16),
    ]

    print("=== Activity Selection ===")
    print(f"Total activities: {len(activities)}")
    selected = activity_selection(activities)
    print(f"Selected activities ({len(selected)}):")
    for s, e in selected:
        print(f"  [{s:2d}, {e:2d}]")

    print("\n=== Timeline Visualization ===")
    selected_set = set(selected)
    print("Time:" + "".join(f"{i:2d}" for i in range(17)))
    for s, e in sorted(activities):
        bar = "  " * s + "━━" * (e - s)
        marker = " ✓" if (s, e) in selected_set else "  "
        print(f"{marker}  [{s},{e}]: {bar}")

    print("\n=== Minimal Removal of Overlapping Intervals ===")
    intervals = [(1, 2), (2, 3), (3, 4), (1, 3)]
    print(f"Intervals: {intervals}")
    print(f"Maximum number of non-overlapping: {max_non_overlapping(intervals)}")
    print(f"Minimum number of removals:     {min_removals_for_non_overlap(intervals)}")

    print("\n=== Comparison of Sorting Criteria (Start Time vs End Time) ===")
    wrong_case = [(0, 10), (1, 2), (3, 4)]
    by_start = sorted(wrong_case, key=lambda x: x[0])
    by_end = sorted(wrong_case, key=lambda x: x[1])

    print(f"Original: {wrong_case}")
    print(f"Sorted by start time: {by_start}")
    print(f"Sorted by end time: {by_end}")

    #Greedy based on start time (wrong)
    wrong_result = []
    last = -1
    for s, e in by_start:
        if s >= last:
            wrong_result.append((s, e))
            last = e
    print(f"Greedy result by start time: {wrong_result} (wrong!)")

    correct = activity_selection(wrong_case)
    print(f"Greedy result by end time: {correct} (correct)")

#Topic: Coin Change — Greedy (When It Is Optimal and When It Fails)
#Time: O(k) Greedy — k = number of coin types
# Space: O(1)


def coin_greedy(coins: list[int], amount: int) -> tuple[int, list[int]]:
    """Greedy Coin Change (use larger coins first).

    Time:  O(k log k + k) = O(k log k)
    Space: O(k) to store results"""
    coins_sorted = sorted(coins, reverse=True)
    result: list[int] = []
    remaining = amount

    for coin in coins_sorted:
        while remaining >= coin:
            result.append(coin)
            remaining -= coin

    return len(result) if remaining == 0 else -1, result


def coin_dp(coins: list[int], amount: int) -> tuple[int, list[int]]:
    """DP Coin Change (guaranteed optimal).

    Time:  O(amount × k)
    Space: O(amount)"""
    INF = float("inf")
    dp = [INF] * (amount + 1)
    dp[0] = 0
    parent = [-1] * (amount + 1)

    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
                parent[i] = coin

    if dp[amount] == INF:
        return -1, []

    #Backtracking
    result: list[int] = []
    curr = amount
    while curr > 0:
        result.append(parent[curr])
        curr -= parent[curr]

    return int(dp[amount]), sorted(result, reverse=True)


def is_greedy_optimal(coins: list[int], max_amount: int = 1000) -> bool:
    """Check if the greedy approach is always optimal for a given set of coins.

    Time:  O(max_amount × k²)
    Space: O(max_amount)"""
    for amount in range(1, max_amount + 1):
        g_count, _ = coin_greedy(coins, amount)
        d_count, _ = coin_dp(coins, amount)
        if g_count != d_count and g_count != -1:
            return False
    return True


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    print("=== Korean Coins (Greedy Optimal) ===")
    korean = [500, 100, 50, 10, 5, 1]
    test_amounts = [1260, 730, 999, 376]
    for amt in test_amounts:
        g_cnt, g_coins = coin_greedy(korean, amt)
        d_cnt, d_coins = coin_dp(korean, amt)
        status = "Match ✓" if g_cnt == d_cnt else "Mismatch ✗"
        print(f"{amt:4d} won: Greedy={g_cnt} coins {g_coins}, DP={d_cnt} coins → {status}")

    print("=== Greedy Failure Examples ===")
    bad_coins = [1, 5, 6, 9]
    for amt in [10, 11, 12]:
        g_cnt, g_coins = coin_greedy(bad_coins, amt)
        d_cnt, d_coins = coin_dp(bad_coins, amt)
        status = "Match ✓" if g_cnt == d_cnt else "Greedy Fails ✗"
        print(f"Coins={bad_coins}, {amt} won:")
        print(f"Greedy: {g_cnt} coins {g_coins}")
        print(f"DP:     {d_cnt} coins {d_coins} → {status}")

    print("=== Analysis of Greedy Optimal Conditions ===")
    coin_sets = [
        ([1, 5, 10, 50, 100, 500], "Korean Coins"),
        ([1, 5, 6, 9], "Greedy Fails"),
        ([1, 2, 5, 10, 20, 50, 100, 200], "Euro Coins"),
        ([1, 3, 4], "Failure Example 2"),
    ]
    for coins, name in coin_sets:
        optimal = is_greedy_optimal(coins, 100)
        print(f"{name:15s} {coins}: Greedy Optimal? {optimal}")

#Topic: Minimum Meeting Rooms
# Time: O(n log n)   Space: O(n)

import heapq


def min_meeting_rooms(intervals: list[tuple[int, int]]) -> int:
    """Minimum number of meeting rooms — using a min heap.

    Idea:
      - Sort start times
      - Store each meeting's end time in a min heap
      - If a new meeting does not overlap with the meeting that ends the earliest, reuse the room

    Time:  O(n log n)
    Space: O(n)"""
    if not intervals:
        return 0

    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    heap: list[int] = []   #End time of each meeting room

    for start, end in sorted_intervals:
        if heap and heap[0] <= start:
            #Reuse the meeting room that ends the earliest
            heapq.heapreplace(heap, end)
        else:
            #Need a new meeting room
            heapq.heappush(heap, end)

    return len(heap)


def min_meeting_rooms_two_pointer(
    intervals: list[tuple[int, int]]
) -> int:
    """Minimum number of meeting rooms — two pointers method.

    Sort start times and end times separately
    → Maximum number of meetings happening simultaneously at any moment

    Time:  O(n log n)
    Space: O(n)"""
    if not intervals:
        return 0

    starts = sorted(s for s, _ in intervals)
    ends = sorted(e for _, e in intervals)

    rooms = 0
    max_rooms = 0
    j = 0   #ends pointer

    for i in range(len(starts)):
        if starts[i] < ends[j]:
            rooms += 1
            max_rooms = max(max_rooms, rooms)
        else:
            rooms -= 1   #One ended
            j += 1

    return max_rooms


def meeting_rooms_schedule(
    intervals: list[tuple[int, int]]
) -> list[list[tuple[int, int]]]:
    """Return the list of meetings assigned to each meeting room.

    Time:  O(n log n)
    Space: O(n)"""
    if not intervals:
        return []

    indexed = sorted(enumerate(intervals), key=lambda x: x[1][0])
    #(end time, meeting room number)
    heap: list[tuple[int, int]] = []
    rooms: list[list[tuple[int, int]]] = []

    for orig_idx, (start, end) in indexed:
        if heap and heap[0][0] <= start:
            end_time, room_idx = heapq.heappop(heap)
            rooms[room_idx].append((start, end))
            heapq.heappush(heap, (end, room_idx))
        else:
            room_idx = len(rooms)
            rooms.append([(start, end)])
            heapq.heappush(heap, (end, room_idx))

    return rooms


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    meetings = [
        (0, 30), (5, 10), (15, 20), (2, 12), (11, 25),
    ]

    print("=== Meeting List ===")
    print(f"{'Meeting':>5} | {'Start':>4} | {'End':>4}")
    print("-" * 18)
    for i, (s, e) in enumerate(meetings):
        print(f"{i:>5} | {s:>4} | {e:>4}")

    min_rooms = min_meeting_rooms(meetings)
    min_rooms_tp = min_meeting_rooms_two_pointer(meetings)
    print(f"Minimum Meeting Rooms (Heap):       {min_rooms}")
    print(f"Minimum Meeting Rooms (Two Pointers): {min_rooms_tp}")
    assert min_rooms == min_rooms_tp

    print("=== Meeting Room Assignment ===")
    schedule = meeting_rooms_schedule(meetings)
    for room_idx, room_meetings in enumerate(schedule):
        print(f"Meeting Room {room_idx + 1}: {room_meetings}")

    print("\n=== Timeline Visualization ===")
    max_time = max(e for _, e in meetings)
    time_header = "Time:" + "".join(f"{t:3d}" for t in range(0, max_time + 1, 3))
    print(f"  {time_header}")
    for i, (s, e) in enumerate(sorted(meetings)):
        bar = "   " * (s // 3) + "━━━" * ((e - s) // 3 + 1)
        print(f"Meeting [{s},{e}]: {bar}")

    print("=== Additional Tests ===")
    test_cases = [
        [(7, 10), (2, 4)],
        [(0, 30), (5, 10), (15, 20)],
        [(1, 5), (2, 6), (3, 7)],
    ]
    for tc in test_cases:
        r = min_meeting_rooms(tc)
        print(f"{tc} → {r} meeting rooms")

#Topic: Greedy Example Collection — Change, Maximum Product, Maximum Array Sum
#Practice various greedy patterns

import heapq


def min_coins_korean(amount: int) -> int:
    """Minimum number of coins as change with Korean coins (greedy optimal).

    Time:  O(1) — fixed coin types
    Space: O(1)"""
    coins = [500, 100, 50, 10, 5, 1]
    count = 0
    for coin in coins:
        count += amount // coin
        amount %= coin
    return count


def max_product_of_two(arr: list[int]) -> int:
    """Maximum product of two numbers in an array.

    Cases: product of the two largest positive numbers vs product of the two smallest negative numbers (negative×negative=positive)

    Time:  O(n)
    Space: O(1)"""
    if len(arr) < 2:
        return 0

    max1 = max2 = float("-inf")   #The two largest numbers
    min1 = min2 = float("inf")    #The two smallest numbers (negative)

    for x in arr:
        if x >= max1:
            max1, max2 = x, max1
        elif x > max2:
            max2 = x

        if x <= min1:
            min1, min2 = x, min1
        elif x < min2:
            min2 = x

    return max(max1 * max2, min1 * min2)


def maximize_array_sum_with_swaps(
    arr: list[int], b: list[int], k: int
) -> int:
    """Maximize the sum of array arr — can replace elements with elements from b up to k times.

    Strategy: replace small elements from arr with large elements from b

    Time:  O(n log n)
    Space: O(n)"""
    arr_sorted = sorted(arr)
    b_sorted = sorted(b, reverse=True)

    for i in range(k):
        if arr_sorted[i] < b_sorted[i]:
            arr_sorted[i] = b_sorted[i]
        else:
            break

    return sum(arr_sorted)


def gas_station(gas: list[int], cost: list[int]) -> int:
    """Gas station problem: find a starting point to make a full circuit.

    Greedy: if total fuel >= total cost, a solution always exists
    Starting point = next point immediately after the tank goes negative

    Time:  O(n)
    Space: O(1)"""
    total_tank = 0
    current_tank = 0
    start = 0

    for i in range(len(gas)):
        diff = gas[i] - cost[i]
        total_tank += diff
        current_tank += diff

        if current_tank < 0:
            start = i + 1
            current_tank = 0

    return start if total_tank >= 0 else -1


def jump_game(nums: list[int]) -> bool:
    """Jump game: can you reach the last position from the first?

    Greedy: keep updating the current maximum reachable position

    Time:  O(n)
    Space: O(1)"""
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + jump)
    return True


def jump_game_min_jumps(nums: list[int]) -> int:
    """Reach the end with the minimum number of jumps.

    Time:  O(n)
    Space: O(1)"""
    jumps = 0
    current_end = 0
    farthest = 0

    for i in range(len(nums) - 1):
        farthest = max(farthest, i + nums[i])
        if i == current_end:
            jumps += 1
            current_end = farthest
            if current_end >= len(nums) - 1:
                break

    return jumps


#── Example Execution ──────────────────────────────────────────────────────────────
if __name__ == "__main__":
    print("=== Korean Coin Change ===")
    for amt in [4860, 1260, 1000, 5]:
        n = min_coins_korean(amt)
        print(f"{amt:5d} won → {n} coins")

    print("=== Maximum Product of Two Numbers ===")
    test_arrs = [
        [1, 5, 3, 2, 4],
        [-10, -3, 5, 2, -1],
        [-5, -4, 1, 2],
        [0, -1, -2, 3],
    ]
    for arr in test_arrs:
        mp = max_product_of_two(arr)
        #Brute-force check
        brute = max(arr[i] * arr[j] for i in range(len(arr)) for j in range(i+1, len(arr)))
        assert mp == brute, f"{arr}: {mp} vs {brute}"
        print(f"{arr}: Maximum Product = {mp}")
    print("All test cases passed ✓")

    print("=== Maximize Array Sum (k swaps) ===")
    a = [1, 2, 3, 4, 5]
    b = [5, 6, 7, 8, 9]
    for k in range(6):
        result = maximize_array_sum_with_swaps(a, b, k)
        print(f"  k={k}: {result}")

    print("=== Gas Station Problem ===")
    gas_cases = [
        ([1, 2, 3, 4, 5], [3, 4, 5, 1, 2]),
        ([2, 3, 4], [3, 4, 3]),
    ]
    for g, c in gas_cases:
        start = gas_station(g, c)
        print(f"gas={g}, cost={c} → Starting Point: {start}")

    print("=== Jump Game ===")
    jump_cases = [
        ([2, 3, 1, 1, 4], True),
        ([3, 2, 1, 0, 4], False),
        ([2, 3, 0, 1, 4], True),
    ]
    for nums, expected in jump_cases:
        can = jump_game(nums)
        min_j = jump_game_min_jumps(nums) if can else -1
        print(f"{nums}: Can Reach={can} (Expected={expected}), Minimum Jumps={min_j}")