Minimal, copy-paste C++ for interval scheduling, activity selection, and greedy on arrays/strings with sorting.

Contents

Greedy Algorithm Overview

Greedy algorithms make locally optimal choices at each step, hoping to find a global optimum. They work well when:

  • The problem has optimal substructure
  • The greedy choice property holds (locally optimal choice leads to global optimum)
  • No need to reconsider previous choices

Key Principles

  1. Greedy Choice Property: A global optimum can be reached by making locally optimal choices
  2. Optimal Substructure: Optimal solution contains optimal solutions to subproblems
  3. No Backtracking: Once a choice is made, it’s never reconsidered

Interval Scheduling

Greedy approach: Sort by end time, always pick the interval that ends earliest.

# Non-overlapping Intervals
def eraseOverlapIntervals(self, intervals):
    if(not intervals) return 0
    sort(intervals.begin(), intervals.end(), [](list[int> a, list[int> b) :
    return a[1] < b[1]  # Sort by end time
    )
    count = 1
    end = intervals[0][1]
    for(i = 1 i < len(intervals) i += 1) :
    if intervals[i][0] >= end:
        count += 1
        end = intervals[i][1]
return len(intervals) - count

Activity Selection

Similar to interval scheduling, select maximum number of non-overlapping activities.

# Maximum number of non-overlapping intervals
def maxNonOverlappingIntervals(self, intervals):
    if(not intervals) return 0
    sort(intervals.begin(), intervals.end(), [](list[int> a, list[int> b) :
    return a[1] < b[1]
    )
    count = 1
    end = intervals[0][1]
    for(i = 1 i < len(intervals) i += 1) :
    if intervals[i][0] >= end:
        count += 1
        end = intervals[i][1]
return count

Fractional Knapsack

Greedy approach: Sort items by value/weight ratio, take items with highest ratio first.

# Fractional Knapsack (not a LeetCode problem, but classic greedy)
struct Item :
value, weight
double ratio
def fractionalKnapsack(self, W, items):
    sort(items.begin(), items.end(), [](Item a, Item b) :
    return a.ratio > b.ratio
    )
    double totalValue = 0.0
    remainingWeight = W
    for item in items:
        if remainingWeight >= item.weight:
            totalValue += item.value
            remainingWeight -= item.weight
             else :
            totalValue += item.value  ((double)remainingWeight / item.weight)
            break
    return totalValue

Greedy on Arrays

Greedy choices on array elements, often with two pointers or sliding window.

# Maximum Subarray (Kadane's Algorithm)
def maxSubArray(self, nums):
    maxSum = nums[0]
    currentSum = nums[0]
    for(i = 1 i < len(nums) i += 1) :
    currentSum = max(nums[i], currentSum + nums[i])
    maxSum = max(maxSum, currentSum)
return maxSum
# Best Time to Buy and Sell Stock II
def maxProfit(self, prices):
    profit = 0
    for(i = 1 i < len(prices) i += 1) :
    if prices[i] > prices[i-1]:
        profit += prices[i] - prices[i-1]
return profit
# Candy - Greedy with sequence tracking
def candy(self, ratings):
    N = len(ratings)
    rtn = 1
    inc = 1, dec = 0, pre = 1
    for(i = 1 i < N i += 1) :
    if ratings[i] >= ratings[i - 1]:
        dec = 0
        (1 if             pre = ratings[i] == ratings[i - 1] * else pre + 1)
        rtn += pre
        inc = pre
         else :
        dec += 1
        if dec == inc:
            dec += 1
        rtn += dec
        pre = 1
return rtn
# Wiggle Subsequence - Greedy with difference tracking
def wiggleMaxLength(self, nums):
    N = len(nums)
    if(N < 2) return N
    prevDiff = nums[1] - nums[0]
    (2 if     rtn = prevDiff != 0 else 1)
    for(i = 2 i < N i += 1) :
    diff = nums[i] - nums[i - 1]
    if((diff > 0  and  prevDiff <= 0)  or
    diff < 0  and  prevDiff >= 0) :
    rtn += 1
    prevDiff = diff
return rtn

Greedy on Strings

Greedy choices when processing strings, often with character frequency or ordering.

# Is Subsequence
def isSubsequence(self, s, t):
    i = 0, j = 0
    while i < s.length()  and  j < t.length():
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == s.length()
# Minimum Swaps to Make Strings Equal - Mismatch pairing
def minimumSwap(self, s1, s2):
    xy = 0, yx = 0
    for(i = 0 i < (int) s1.length() i += 1) :
    if s1[i] == 'x'  and  s2[i] == 'y':
        xy += 1
         else if(s1[i] == 'y'  and  s2[i] == 'x') :
        yx += 1
if (xy + yx) % 2 == 1:
    return -1  # Impossible if odd total mismatches
return xy / 2 + yx / 2 + xy % 2 + yx % 2
# Construct K Palindrome Strings - Frequency-based greedy
def canConstruct(self, s, k):
    right = s.length()
    occ[26] = :0
for ch in s:
    occ[ch - 'a']++
left = 0
for(i = 0 i < 26 i += 1) :
if occ[i] % 2 == 1:
    left += 1
left = max(left, 1)
return left <= k  and  k <= right

Greedy with Sorting

Many greedy problems require sorting first to make optimal choices.

# Assign Cookies
def findContentChildren(self, g, s):
    g.sort()
    s.sort()
    i = 0, j = 0
    count = 0
    while i < len(g)  and  j < len(s):
        if s[j] >= g[i]:
            count += 1
            i += 1
        j += 1
    return count
# Array Partition - Maximize sum of minimums
def arrayPairSum(self, nums):
    nums.sort()
    sum = 0
    for(i = 0 i < (int)len(nums) i += 2) :
    sum += nums[i]
return sum
# Maximum Units on a Truck - Fractional knapsack style
def maximumUnits(self, boxTypes, truckSize):
    sort(boxTypes.begin(), boxTypes.end(), [](u, v):
    return u[1] > v[1]  # Sort by units per box (descending)
    )
    remainSize = truckSize
    maximumUnits = 0
    for boxType in boxTypes:
        if(remainSize == 0) break
        cnt = min(remainSize, boxType[0])
        maximumUnits += cnt  boxType[1]
        remainSize -= cnt
    return maximumUnits
# Minimum Cost to Move Chips - Parity-based greedy
def minCostToMoveChips(self, position):
    even = 0, odd = 0
    for pos in position:
        if pos % 2 == 0:
            odd += 1  # Count even positions
             else :
            even += 1  # Count odd positions
    return min(odd, even)  # Move minority parity to majority
# Two City Scheduling - Sort by cost difference
def twoCitySchedCost(self, costs):
    sort(costs.begin(), costs.end(), [](u, autov) :
    return (u[0] - u[1] < v[0] - v[1])
    )
    total = 0
    N = len(costs) / 2
    for(i = 0 i < N i += 1) :
    total += costs[i][0] + costs[i + N][1]
return total
# Find Valid Matrix Given Row and Column Sums - Greedy two pointers
def restoreMatrix(self, rowSum, colSum):
    N = len(rowSum), M = len(colSum)
    list[list[int>> matrix(N, list[int>(M, 0))
    i = 0, j = 0
    while i < N  and  j < M:
        v = min(rowSum[i], colSum[j])
        matrix[i][j] = v
        rowSum[i] -= v
        colSum[j] -= v
        if(rowSum[i] == 0) i += 1
        if(colSum[j] == 0) j += 1
    return matrix
# Queue Reconstruction by Height
def reconstructQueue(self, people):
    sort(people.begin(), people.end(), [](list[int> a, list[int> b) :
    (a[1] < b[1] if         return a[0] == b[0] * else a[0] > b[0])
    )
    list[list[int>> result
    for person in people:
        result.insert(result.begin() + person[1], person)
    return result

Easy Problems

ID Title Link Solution
455 Assign Cookies Link Solution
860 Lemonade Change Link Solution
392 Is Subsequence Link Solution
406 Queue Reconstruction by Height Link Solution
53 Maximum Subarray Link Solution
435 Non-overlapping Intervals Link Solution
452 Minimum Number of Arrows to Burst Balloons Link Solution
561 Array Partition Link Solution
1029 Two City Scheduling Link Solution
122 Best Time to Buy and Sell Stock II Link Solution
1710 Maximum Units on a Truck Link Solution
1217 Minimum Cost to Move Chips to The Same Position Link Solution

Medium Problems

ID Title Link Solution
763 Partition Labels Link -
621 Task Scheduler Link -
435 Non-overlapping Intervals Link Solution
55 Jump Game Link Solution
1094 Car Pooling Link Solution
45 Jump Game II Link Solution
134 Gas Station Link -
1024 Video Stitching Link -
1247 Minimum Swaps to Make Strings Equal Link Solution
1400 Construct K Palindrome Strings Link Solution
1605 Find Valid Matrix Given Row and Column Sums Link Solution
376 Wiggle Subsequence Link Solution

Hard Problems

ID Title Link Solution
135 Candy Link Solution
871 Minimum Number of Refueling Stops Link -
818 Race Car Link -
410 Split Array Largest Sum Link -
420 Strong Password Checker Link -
68 Text Justification Link -
76 Minimum Window Substring Link -
1799 Maximize Score After N Operations Link -

Common Greedy Patterns

1. Interval Problems

  • Sort by end time
  • Always pick the interval that ends earliest
  • Examples: Non-overlapping Intervals, Minimum Arrows to Burst Balloons

2. Two Pointers

  • Use two pointers to make greedy choices
  • Examples: Is Subsequence, Assign Cookies

3. Sorting + Greedy

  • Sort first, then apply greedy strategy
  • Examples: Queue Reconstruction by Height, Two City Scheduling

4. Local Optimization

  • Make best local choice at each step
  • Examples: Best Time to Buy and Sell Stock II, Maximum Subarray

5. Jump Problems

  • Greedy choice: jump as far as possible
  • Examples: Jump Game, Jump Game II

6. Scheduling Problems

  • Sort and schedule optimally
  • Examples: Task Scheduler, Car Pooling

Key Insights

  1. When to use Greedy:
    • Problem has optimal substructure
    • Greedy choice property holds
    • No need to reconsider previous choices
  2. Common Mistakes:
    • Not sorting when needed
    • Wrong sorting criteria
    • Not considering edge cases
    • Assuming greedy always works (need to prove correctness)
  3. Proving Greedy Correctness:
    • Show greedy choice property
    • Show optimal substructure
    • Use exchange argument or contradiction
  • Dynamic Programming (when greedy doesn’t work)
  • Sorting Algorithms
  • Interval Problems
  • Two Pointers
  • Sliding Window

References

More templates