Greedy Algorithm Patterns: Interval Scheduling, Activity Selection, and More

Greedy algorithms make the locally optimal choice at each step, hoping it leads to a globally optimal solution. Unlike dynamic programming, greedy does not reconsider past decisions. It works when the problem has the greedy choice property: a locally optimal choice is part of some globally optimal solution. This guide covers the most common greedy patterns on LeetCode.

When Greedy Works

Greedy is correct when:

1. Greedy choice property: A globally optimal solution can be built by making locally optimal choices.
2. Optimal substructure: The remaining subproblem after making the greedy choice is also an optimization problem.

When in doubt, try to prove by exchange argument: show that swapping any non-greedy choice for the greedy one does not make the solution worse.

Pattern 1: Interval Scheduling

Merge Intervals (LC 56)

Sort by start time, then merge overlapping intervals.

def merge(intervals: list[list[int]]) -> list[list[int]]:
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            # Overlapping -- extend the current interval
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    
    return merged

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

// Java version
public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    List<int[]> merged = new ArrayList<>();
    merged.add(intervals[0]);
    
    for (int i = 1; i < intervals.length; i++) {
        int[] last = merged.get(merged.size() - 1);
        if (intervals[i][0] <= last[1]) {
            last[1] = Math.max(last[1], intervals[i][1]);
        } else {
            merged.add(intervals[i]);
        }
    }
    return merged.toArray(new int[0][]);
}

Non-Overlapping Intervals (LC 435)

Find the minimum number of intervals to remove so the rest do not overlap. This is the classic activity selection problem in disguise.

def eraseOverlapIntervals(intervals: list[list[int]]) -> int:
    # Sort by end time -- greedy: keep intervals that end earliest
    intervals.sort(key=lambda x: x[1])
    
    count = 0
    prev_end = float('-inf')
    
    for start, end in intervals:
        if start >= prev_end:
            # No overlap -- keep this interval
            prev_end = end
        else:
            # Overlap -- remove this interval (increment count)
            count += 1
    
    return count

print(eraseOverlapIntervals([[1,2],[2,3],[3,4],[1,3]]))  # 1
print(eraseOverlapIntervals([[1,2],[1,2],[1,2]]))         # 2

Sorted by end time:
[1,2] [2,3] [1,3] [3,4]
      
Pick [1,2] (end=2)
Pick [2,3] (start=2 >= end=2, no overlap)
Skip [1,3] (start=1 < end=3, overlap!)
Pick [3,4] (start=3 >= end=3, no overlap)

Removed 1 interval. Kept 3.

Insert Interval (LC 57)

def insert(intervals: list[list[int]], newInterval: list[int]) -> list[list[int]]:
    result = []
    i = 0
    n = len(intervals)
    
    # Add all intervals before newInterval
    while i < n and intervals[i][1] < newInterval[0]:
        result.append(intervals[i])
        i += 1
    
    # Merge overlapping intervals with newInterval
    while i < n and intervals[i][0] <= newInterval[1]:
        newInterval[0] = min(newInterval[0], intervals[i][0])
        newInterval[1] = max(newInterval[1], intervals[i][1])
        i += 1
    result.append(newInterval)
    
    # Add remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1
    
    return result

print(insert([[1,3],[6,9]], [2,5]))  # [[1,5],[6,9]]

Meeting Rooms II (LC 253)

Find the minimum number of meeting rooms required.

import heapq

def minMeetingRooms(intervals: list[list[int]]) -> int:
    if not intervals:
        return 0
    
    intervals.sort(key=lambda x: x[0])
    heap = []  # tracks end times of ongoing meetings
    
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heappop(heap)  # reuse a room
        heapq.heappush(heap, end)
    
    return len(heap)

print(minMeetingRooms([[0,30],[5,10],[15,20]]))  # 2
print(minMeetingRooms([[7,10],[2,4]]))            # 1

Pattern 2: Jump Games

Jump Game (LC 55)

Can you reach the last index? Greedily track the farthest reachable position.

def canJump(nums: list[int]) -> bool:
    farthest = 0
    
    for i in range(len(nums)):
        if i > farthest:
            return False
        farthest = max(farthest, i + nums[i])
    
    return True

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

Jump Game II (LC 45)

Find the minimum number of jumps to reach the end.

def jump(nums: list[int]) -> int:
    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

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

// Java version
public int jump(int[] nums) {
    int jumps = 0, currentEnd = 0, farthest = 0;
    for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(farthest, i + nums[i]);
        if (i == currentEnd) {
            jumps++;
            currentEnd = farthest;
        }
    }
    return jumps;
}

Pattern 3: Gas Station (LC 134)

def canCompleteCircuit(gas: list[int], cost: list[int]) -> int:
    if sum(gas) < sum(cost):
        return -1  # not enough total gas
    
    start = 0
    tank = 0
    
    for i in range(len(gas)):
        tank += gas[i] - cost[i]
        if tank < 0:
            start = i + 1  # cannot start at or before i
            tank = 0
    
    return start

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

The greedy insight: if total gas >= total cost, a solution exists. If the tank goes negative at station i, no station between the start and i can be a valid starting point, so jump to i+1.

Pattern 4: Task Scheduling

Task Scheduler (LC 621)

Schedule tasks with a cooldown period. Greedy: schedule the most frequent task first.

from collections import Counter

def leastInterval(tasks: list[str], n: int) -> int:
    freq = Counter(tasks)
    max_freq = max(freq.values())
    max_count = sum(1 for f in freq.values() if f == max_freq)
    
    # Formula: (max_freq - 1) * (n + 1) + max_count
    # But if many tasks, total task count might exceed this
    result = (max_freq - 1) * (n + 1) + max_count
    return max(result, len(tasks))

print(leastInterval(["A","A","A","B","B","B"], 2))  # 8
print(leastInterval(["A","A","A","B","B","B"], 0))  # 6

Pattern 5: Assign and Distribute

Assign Cookies (LC 455)

Match children (greed factors) with cookies (sizes). Greedily assign the smallest sufficient cookie to each child.

def findContentChildren(g: list[int], s: list[int]) -> int:
    g.sort()
    s.sort()
    child = 0
    cookie = 0
    
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1  # satisfied
        cookie += 1
    
    return child

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

Partition Labels (LC 763)

def partitionLabels(s: str) -> list[int]:
    # Find the last occurrence of each character
    last = {c: i for i, c in enumerate(s)}
    
    partitions = []
    start = 0
    end = 0
    
    for i, c in enumerate(s):
        end = max(end, last[c])
        if i == end:
            partitions.append(end - start + 1)
            start = i + 1
    
    return partitions

print(partitionLabels("ababcbacadefegdehijhklij"))
# [9, 7, 8]

Pattern 6: Huffman-Style Greedy

Minimum Cost to Connect Sticks (LC 1167)

Always connect the two shortest sticks first.

import heapq

def connectSticks(sticks: list[int]) -> int:
    heapq.heapify(sticks)
    total_cost = 0
    
    while len(sticks) > 1:
        first = heapq.heappop(sticks)
        second = heapq.heappop(sticks)
        cost = first + second
        total_cost += cost
        heapq.heappush(sticks, cost)
    
    return total_cost

print(connectSticks([2, 4, 3]))  # 14 (2+3=5, 5+4=9, total=14)
print(connectSticks([1, 8, 3, 5]))  # 30

Greedy vs DP: When Each Applies

Key Takeaways

Greedy algorithms work when the locally optimal choice is always part of a globally optimal solution. For interval problems, sort by end time and greedily pick non-overlapping intervals. For jump problems, track the farthest reachable position. For scheduling, handle the most constrained element first. Always verify greedy correctness with an exchange argument or counterexample. If greedy does not work, try dynamic programming. The most common mistake is applying greedy when the problem actually requires DP — test with small examples to check.