Greedy & Interval Problems

This lesson on Greedy & Interval Problems is hands-on and example-driven. You will learn to formulate, implement, and mathematically prove greedy solutions for the interval scheduling and activity selection problem. You can determine optimal non-overlapping activity sets in O(N log N) time by sorting intervals by earliest finishing time and verifying correctness via mathematical induction.

What You'll Be Able To Do

• Formalize activity scheduling intervals using start and finish time constraints.
• Implement the Earliest Finish Time greedy selection algorithm in Python.
• Calculate the runtime complexity bound by isolating the dominant sorting phase.
• Construct an inductive correctness proof demonstrating non-overlapping compatibility.
• Identify edge cases where improper sorting heuristics fail to produce optimal sets.

Detailed Concept Walkthrough

1. Interval Compatibility and Mathematical Formalization

Interval scheduling models mutually exclusive tasks requesting access to a shared resource over continuous time intervals. An activity is valid if its execution window does not collide with previously scheduled tasks.

• Mechanism: Each activity J is defined as a half-open or closed interval bounded by start time S_J and finish time F_J, where S_J < F_J.
• Compatibility Rule: Two activities M and N are compatible if and only if they do not overlap, formally expressed as S_N >= F_M or S_M >= F_N.
• Execution Flow: A candidate activity N can only be admitted into a selected schedule set A if its start time S_N occurs at or after the finish time F_M of the most recently admitted activity M.

# Define an activity structure and compatibility check
class Activity:
    def __init__(self, name, start, finish):
        self.name = name
        self.start = start
        self.finish = finish

def is_compatible(prev_activity, next_activity):
    # Compatible if the next activity starts after or when the previous finishes
    return next_activity.start >= prev_activity.finish

Key Takeaway: Two activities are mutually compatible if and only if the later activity starts at or after the earlier activity finishes.

2. The Earliest Finish Time Greedy Heuristic

Selecting the compatible activity with the earliest finish time maximizes the remaining contiguous time available for all future candidate activities.

• Mechanism: At each decision point, evaluate all remaining candidates and pick the one that frees up the shared resource at the earliest possible moment.
• Under the Hood: Sorting all intervals primarily by finish time F_J in ascending order aligns all candidates so that a single linear sweep can make locally optimal choices.
• Nuance: Alternative greedy heuristics—such as sorting by earliest start time, shortest duration, or fewest conflicts—fail counterexamples and do not guarantee global optimality.

# Greedy activity selection using earliest finish time
def select_activities(activities):
    # Step 1: Sort activities by finishing time ascending
    sorted_activities = sorted(activities, key=lambda x: x.finish)
    selected = []
    last_finish = float('-inf')
    
    # Step 2: Greedily pick compatible intervals
    for act in sorted_activities:
        if act.start >= last_finish:
            selected.append(act)
            last_finish = act.finish
    return selected

Key Takeaway: Sorting by earliest finish time leaves the maximal remaining time window for subsequent intervals, producing a globally maximal set.

3. Complexity Analysis and Dominance

The computational cost of activity selection is dominated by the initial sorting stage, while the selection pass runs in linear time.

• Mechanism: The algorithm comprises two phases: sorting N activities by finish time, followed by a single iterative scan through the sorted array.
• Under the Hood: Sorting requires O(N log N) comparisons using comparison-based sorts like Merge Sort or Timsort, while the single pass checks S_N >= F_M in O(1) per element, totaling O(N).
• Complexity Dominance: Because O(N log N) dominates O(N), the overall tight upper bound for the algorithm is O(N log N) time and O(N) or O(1) auxiliary space.

# Time complexity breakdown
def measure_activity_selector(intervals):
    # 1. Sorting step: O(N log N)
    intervals.sort(key=lambda item: item[1])
    
    # 2. Linear scan step: O(N)
    count = 0
    curr_end = -1
    for start, finish in intervals:
        if start >= curr_end:
            count += 1
            curr_end = finish
    return count  # Total time: O(N log N)

Key Takeaway: The overall runtime is strictly bound by the O(N log N) sorting step since the subsequent greedy selection pass takes O(N).

4. Inductive Correctness Proof

Mathematical induction verifies that the greedy choice at each step preserves an optimal and strictly compatible schedule.

• Base Case: The base case is established on an empty set or a single interval selection, which is trivially non-overlapping and optimal.
• Inductive Step: Assume the greedy choice holds compatible for k elements; when evaluating candidate k + 1, it is either added if S_{k+1} >= F_k (maintaining compatibility) or rejected.
• Optimality Guarantee: Because the chosen interval finishes earliest, any alternative optimal solution can be transformed into the greedy solution without reducing the total number of activities.

# Formal verification invariant check
def verify_schedule(schedule):
    # Base case: Empty or 1 element is always valid
    if len(schedule) <= 1:
        return True
    # Inductive verification: Check pairwise compatibility across all k
    for i in range(1, len(schedule)):
        if schedule[i].start < schedule[i-1].finish:
            return False  # Violation of inductive hypothesis
    return True

Key Takeaway: Mathematical induction proves that making locally optimal earliest-finish choices maintains invariant compatibility across all step transitions.

Topics Covered in Greedy & Interval Problems

1. Interval Scheduling Overview (0:00 - 1:21) — The instructor defines the interval scheduling problem and frames the objective of maximizing compatible non-overlapping activities.
2. Notation and Compatibility (1:23 - 1:52) — Formal notations for start and finish times are introduced alongside the mathematical inequality required for compatibility.
3. Earliest Finish Time Rule (1:53 - 3:07) — The instructor explains why selecting tasks by earliest finish time optimizes remaining available schedule space.
4. Pseudocode Implementation (3:07 - 4:03) — A step-by-step walkthrough shows how to sort intervals, initialize tracking variables, and iteratively select compatible tasks.
5. Complexity Analysis (4:04 - 4:54) — The instructor calculates the overall computational complexity by identifying sorting as the dominant O(N log N) step.
6. Inductive Correctness Proof (4:55 - 6:50) — Mathematical induction is applied across base cases and inductive steps to prove the greedy algorithm guarantees optimality.

DSA for Interviews Cheat Sheet

• sorted(intervals, key=lambda x: x[1]) — Sorts intervals in ascending order by finish time

  sorted_intervals = sorted(intervals, key=lambda x: x[1])
  

• S_N >= F_M — Mathematical condition establishing compatibility between two intervals

  is_compat = next_interval.start >= prev_interval.finish
  

• greedy_select(sorted_list) — Iterates once to greedily collect non-overlapping intervals

  res = [act for act in acts if act.start >= last_end]
  

• O(N log N) — Overall time complexity bound dominated by sorting

  # Dominated by Merge Sort / Timsort
  

• O(N) — Linear time complexity of greedy pass

  # Single loop through N elements
  

Comparison Table

Common Pitfalls

• Mistake: Sorting activities by start time instead of finish time. Avoid: Always sort intervals by finish time to leave maximum remaining time.
• Mistake: Comparing candidate start time with candidate finish time instead of previous finish. Avoid: Compare candidate start time strictly against the last accepted interval finish.
• Mistake: Assuming the linear scan determines overall algorithmic complexity. Avoid: Account for the sorting phase which dominates runtime at O(N log N).

FAQs

• Why does sorting by earliest start time fail to yield a maximal set? An activity that starts very early might have an extremely long duration, blocking numerous shorter compatible activities.
• Can two activities share an exact boundary timestamp? Yes, if an activity starts at the exact time another finishes (S_N = F_M), they satisfy the compatibility condition S_N >= F_M.
• What is the space complexity of the greedy interval selector? It requires O(N) auxiliary space to store the sorted output and selected schedule, or O(1) auxiliary space if sorted in place.