PyDSA Academy — Python & DSA Learning

What is a Greedy Algorithm?

A greedy algorithm makes the locally optimal choice at each step, hoping to find a global optimum.

When greedy works: The problem has the greedy choice property — a local optimal choice leads to a global optimal solution.

When it fails: When you need to consider future consequences (use DP instead).

Interval Scheduling

Activity Selection (Maximum Non-Overlapping Intervals)

def activity_selection(intervals):
    """Select max number of non-overlapping intervals
    Strategy: always pick the interval that ends earliest
    """
    # Sort by end time
    intervals.sort(key=lambda x: x[1])
    count = 0
    last_end = float('-inf')

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

intervals = [[1,2],[2,3],[3,4],[1,3]]
print(activity_selection(intervals))  # 3 (non-overlapping)

Merge Overlapping Intervals

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]

    for start, end in intervals[1:]:
        if start <= merged[-1][1]:   # overlaps
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]

Minimum Number of Platforms

def min_platforms(arrivals, departures):
    """Minimum platforms needed at a train station"""
    arrivals.sort()
    departures.sort()
    platforms = 1
    max_platforms = 1
    i, j = 1, 0

    while i < len(arrivals) and j < len(departures):
        if arrivals[i] <= departures[j]:
            platforms += 1
            i += 1
            max_platforms = max(max_platforms, platforms)
        else:
            platforms -= 1
            j += 1
    return max_platforms

Jump Game Variants

Can Reach End?

def can_jump(nums):
    """Can you reach the last index?"""
    max_reach = 0
    for i, jump in enumerate(nums):
        if i > max_reach:
            return False
        max_reach = max(max_reach, i + jump)
    return True

print(can_jump([2, 3, 1, 1, 4]))  # True
print(can_jump([3, 2, 1, 0, 4]))  # False

Minimum Jumps

def jump(nums):
    """Minimum jumps to reach the last index"""
    n = len(nums)
    jumps = 0
    current_end = 0
    farthest = 0

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

print(jump([2, 3, 1, 1, 4]))   # 2
print(jump([2, 3, 0, 1, 4]))   # 2

Task Scheduling

Assign Cookies

def find_content_children(greed, size):
    """Give each child at most one cookie; maximize satisfied children"""
    greed.sort()
    size.sort()
    child, cookie = 0, 0
    while child < len(greed) and cookie < len(size):
        if size[cookie] >= greed[child]:
            child += 1
        cookie += 1
    return child

print(find_content_children([1, 2, 3], [1, 1]))     # 1
print(find_content_children([1, 2], [1, 2, 3]))      # 2

Gas Station

def can_complete_circuit(gas, cost):
    """Find starting station to complete circular route"""
    total = 0
    tank = 0
    start = 0

    for i in range(len(gas)):
        gain = gas[i] - cost[i]
        total += gain
        tank += gain
        if tank < 0:
            start = i + 1
            tank = 0

    return start if total >= 0 else -1

print(can_complete_circuit([1,2,3,4,5], [3,4,5,1,2]))  # 3

Huffman Coding

import heapq

def huffman_codes(freq):
    """Build optimal prefix-free encoding"""
    heap = [(f, i, ch) for i, (ch, f) in enumerate(freq.items())]
    heapq.heapify(heap)

    codes = {}
    counter = len(freq)

    while len(heap) > 1:
        f1, _, n1 = heapq.heappop(heap)
        f2, _, n2 = heapq.heappop(heap)

        merged = (f1 + f2, counter, {**{k: '0' + v for k, v in (n1 if isinstance(n1, dict) else {n1: ''}).items()},
                                     **{k: '1' + v for k, v in (n2 if isinstance(n2, dict) else {n2: ''}).items()}})
        heapq.heappush(heap, merged)
        counter += 1

    return heap[0][2] if heap else {}

freq = {'a': 5, 'b': 9, 'c': 12, 'd': 13, 'e': 16, 'f': 45}
codes = huffman_codes(freq)
print(codes)

Exercises

Exercise 1: Two City Scheduling

Send N people to two cities at minimum cost. Exactly N/2 to each.

Solution:

def two_city_sched_cost(costs):
    # Sort by difference: cost_A - cost_B
    # Send people with lowest (costA - costB) to city A
    costs.sort(key=lambda x: x[0] - x[1])
    n = len(costs) // 2
    return sum(costs[i][0] for i in range(n)) + sum(costs[i][1] for i in range(n, 2*n))

print(two_city_sched_cost([[10,20],[30,200],[400,50],[30,20]]))  # 110

Exercise 2: Partition Labels

Partition string so each letter appears in at most one part; maximize parts.