Interval Scheduling Maximization: Complete Solution and Analysis

Introduction and Core Concepts

Interval Scheduling Maximization is one of the most fundamental and elegant problems in the study of greedy algorithms. At its core, the problem asks a deceptively simple question: given a set of intervals, each with a start time and a finish time, how can we select the largest possible subset of intervals such that no two selected intervals overlap? This problem, often called the Activity Selection Problem or Unweighted Interval Scheduling, appears in countless practical scenarios and serves as a canonical example of when a greedy strategy is not only efficient but provably optimal.

Formally, we are given a set of n intervals I = {1, 2, ..., n} where each interval i is defined by a start time s(i) and a finish time f(i) with s(i) < f(i). Two intervals i and j are said to be compatible if they do not overlap, meaning f(i) <= s(j) or f(j) <= s(i). The goal of interval scheduling maximization is to find a maximum-size subset of mutually compatible intervals. Unlike optimization problems that seek to maximize total weight or value, this unweighted variant treats every interval equally; the objective is purely to maximize the count of scheduled intervals.

Why does this problem matter so much in computer science education and practice? First, it demonstrates the power of the greedy paradigm: making a locally optimal choice at each step can lead to a globally optimal solution, but only if the choice is made correctly. Second, it introduces critical proof techniques such as the exchange argument and the concept of greedy stays ahead, which are essential for reasoning about algorithm correctness. Third, its efficiency is remarkable. A naive brute-force approach would examine all 2^n subsets, which is computationally infeasible for large n, while the optimal greedy algorithm solves it in O(n log n) time. Understanding this problem provides a foundation for tackling more complex scheduling, resource allocation, and optimization challenges.

Key Definitions and Assumptions

To reason precisely about the problem, we must clarify several assumptions. We assume intervals are half-open [s, f), meaning an interval finishing at time t is compatible with another interval starting at exactly t. This is the standard model for scheduling resources like classrooms or processors where back-to-back usage is allowed. If intervals are considered closed [s, f], then f(i) < s(j) would be required for compatibility, but the algorithmic logic remains identical with a strict inequality.

We also assume that all intervals are known in advance (offline problem) and that their start and finish times can be compared and sorted. The problem does not consider priorities, weights, or durations initially; those extensions lead to different variants such as Weighted Interval Scheduling, which requires dynamic programming. The beauty of the unweighted version is that structure alone — the ordering of finish times — is sufficient to guarantee optimality without any additional information.

Why Greedy Works Here

Not all optimization problems can be solved greedily. For interval scheduling maximization, the greedy approach works because the problem exhibits two key properties: the greedy-choice property and optimal substructure. The greedy-choice property means there exists an optimal solution that includes the greedy choice (the interval that finishes earliest). Optimal substructure means that after making the greedy choice, the remaining subproblem — finding an optimal schedule among intervals compatible with the chosen one — is itself an instance of the same problem. These properties together ensure that iteratively picking the earliest-finishing compatible interval never harms the ability to reach a global optimum.

How It Works

The mechanism behind interval scheduling maximization is the Earliest Finish Time (EFT) first strategy. The algorithm is strikingly simple: sort all intervals by their finish times in non-decreasing order, then iterate through the sorted list, selecting an interval if it is compatible with the last selected interval. The first interval in the sorted order is always selected, as it leaves the maximum possible remaining time for future selections. This strategy is counterintuitive to beginners who might propose alternative heuristics, but it is the only one among common natural heuristics that guarantees optimality.

Consider why alternative greedy strategies fail. Selecting the interval with the earliest start time can be disastrous; a very long interval that starts early may block many shorter, more numerous intervals. Selecting the shortest interval first also fails; a short interval in the middle of the timeline can block two other intervals that would otherwise both fit. Selecting the interval with the fewest conflicts seems promising but is also not optimal and is more expensive to compute. Only the earliest finish time strategy ensures that the resource becomes free as soon as possible, maximizing the opportunity for subsequent intervals.

The theoretical justification for EFT relies on an exchange argument. Suppose we have an optimal solution OPT and a greedy solution GREEDY. Let i1 be the interval with the earliest finish time. We can prove that there exists an optimal solution that includes i1. If OPT already includes i1, we are done. If not, let j be the first interval in OPT (when sorted by finish time). Since f(i1) <= f(j) by definition, we can replace j with i1 in OPT without creating any conflicts and without reducing the size of the solution. Repeating this exchange for the remaining subproblem inductively proves that GREEDY is optimal. This proof also illustrates the greedy stays ahead principle: after k selections, the finish time of the k-th interval in GREEDY is always less than or equal to the finish time of the k-th interval in any other feasible solution.

The Algorithm in Detail

The algorithm proceeds in two phases. Phase one is sorting, which dominates the running time. Phase two is a single linear scan. We maintain a variable last_finish, initialized to negative infinity, representing the finish time of the most recently selected interval. For each interval (s, f) in sorted order, we check if s >= last_finish. If true, the interval is compatible, so we select it and update last_finish = f. If false, we skip it. The algorithm is deterministic if we break ties consistently, for example by sorting intervals with the same finish time by start time.

This process is inherently online in its scan phase but requires offline sorting. It is also stable and requires only O(1) additional state beyond the sorted list. The decision at each step is irrevocable; once an interval is skipped, it is never reconsidered, and once selected, it is never removed. This irrevocability is characteristic of greedy algorithms and is what makes them so efficient when correct.

Intuition with a Timeline

Visualize the intervals on a timeline. The earliest finishing interval occupies the leftmost possible endpoint. By choosing it, we carve off the smallest possible prefix of the timeline and leave the largest possible suffix for the remaining problem. Any other choice would consume more of the timeline upfront and can only reduce the space available for future intervals. This geometric intuition aligns perfectly with the formal proof and helps explain why the algorithm is optimal for maximizing count but not for maximizing total duration or weight, where consuming more timeline might be justified by higher value.

Implementation

Implementing interval scheduling maximization in Python is straightforward, but production-quality code must handle edge cases, input validation, and clear return values. The following implementations demonstrate increasing levels of robustness and utility, from a minimal core algorithm to a more complete solution suitable for integration into larger systems.

The core logic remains the same across all variants: sort by finish time and greedily select compatible intervals. Python's built-in sort is stable and runs in O(n log n) time using Timsort, making it ideal for this step. The key is to use a key function that extracts the finish time, and optionally the start time as a tie-breaker to ensure deterministic behavior.

# Basic interval scheduling maximization
# Returns the maximum-size set of non-overlapping intervals
def interval_scheduling_maximization(intervals):
    """
    intervals: list of tuples (start, finish)
    Returns: list of selected intervals sorted by finish time
    """
    if not intervals:
        return []

    # Sort by finish time (earliest first)
    intervals_sorted = sorted(intervals, key=lambda x: x[1])

    selected = []
    last_finish = float('-inf')

    for start, finish in intervals_sorted:
        # Compatible if start is at or after last selected finish
        if start >= last_finish:
            selected.append((start, finish))
            last_finish = finish

    return selected

# Example usage
intervals = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
print(interval_scheduling_maximization(intervals))
# Output: [(1, 4), (5, 7), (8, 11), (12, 16)]

The basic implementation above is concise and captures the essence of the algorithm. However, it assumes valid input and does not provide diagnostics. In real applications, intervals may be malformed, contain invalid times, or be empty. The next implementation adds validation and handles tie-breaking explicitly.

def schedule_with_validation(intervals):
    """
    Robust version with validation and deterministic tie-breaking.
    Raises ValueError for invalid intervals where start > finish.
    """
    if not intervals:
        return []

    # Validate all intervals
    for s, f in intervals:
        if s > f:
            raise ValueError(f"Invalid interval ({s}, {f}): start > finish")
        if s == f:
            # Zero-length intervals are allowed but handled carefully
            # They are compatible only if they don't overlap
            pass

    # Sort by finish time, then by start time for determinism
    sorted_intervals = sorted(intervals, key=lambda x: (x[1], x[0]))

    result = []
    last_end = float('-inf')

    for s, f in sorted_intervals:
        if s >= last_end:
            result.append((s, f))
            last_end = f

    return result

# Handles edge cases
print(schedule_with_validation([]))  # []
print(schedule_with_validation([(1, 2), (2, 3), (3, 4)]))  # all three
# schedule_with_validation([(5, 3)])  # raises ValueError

For larger systems, it is often useful to encapsulate intervals as objects and return both the count and the actual schedule. This object-oriented approach improves readability and makes it easier to extend the solution to track additional metadata such as interval IDs or associated resources.

class Interval:
    def __init__(self, start, finish, label=None):
        self.start = start
        self.finish = finish
        self.label = label
    def __repr__(self):
        return f"Interval({self.start}, {self.finish}, '{self.label}')"

def schedule_objects(intervals):
    """
    Works with Interval objects and preserves labels.
    Returns selected objects in order of selection.
    """
    if not intervals:
        return []

    # Sort objects by finish time
    sorted_intervals = sorted(intervals, key=lambda x: x.finish)

    selected = []
    last_finish = float('-inf')

    for iv in sorted_intervals:
        if iv.start >= last_finish:
            selected.append(iv)
            last_finish = iv.finish

    return selected

# Example with labeled intervals
objs = [Interval(1, 4, "A"), Interval(5, 7, "B"), Interval(3, 5, "C"), Interval(8, 11, "D")]
chosen = schedule_objects(objs)
print(chosen)  # [Interval(1, 4, 'A'), Interval(5, 7, 'B'), Interval(8, 11, 'D')]
print(f"Maximum activities: {len(chosen)}")

Finally, many interview and production scenarios ask not just for the schedule but also for the ability to process streaming input or to count the maximum number without storing all intervals. The following variant demonstrates a memory-efficient approach that processes intervals sorted externally and only keeps the count and last finish time, which is useful when n is very large.

def max_activities_count(intervals):
    """
    Returns only the count of maximum non-overlapping intervals.
    Memory efficient: O(1) extra space beyond sorting.
    Useful for large datasets where storing the full schedule is unnecessary.
    """
    if not intervals:
        return 0

    intervals_sorted = sorted(intervals, key=lambda x: x[1])
    count = 0
    last_finish = float('-inf')

    for s, f in intervals_sorted:
        if s >= last_finish:
            count += 1
            last_finish = f

    return count

def schedule_from_input():
    """
    Example of reading intervals from standard input.
    Input format: n followed by n lines of 'start finish'
    """
    import sys
    data = sys.stdin.read().strip().split()
    if not data:
        return
    n = int(data[0])
    intervals = []
    idx = 1
    for i in range(n):
        if idx + 1 >= len(data):
            break
        s = int(data[idx]); f = int(data[idx+1])
        intervals.append((s, f))
        idx += 2
    result = interval_scheduling_maximization(intervals)
    print(f"Selected {len(result)} intervals: {result}")

# Quick test for count-only version
print(max_activities_count([(1, 3), (2, 4), (3, 5)]))  # 2

Step-by-Step Example

To solidify understanding, let us walk through a concrete example with 8 intervals. Consider the following set representing lecture times that need to be scheduled in a single classroom: A(1, 4), B(3, 5), C(0, 6), D(5, 7), E(3, 9), F(5, 9), G(6, 10), H(8, 11). The goal is to select the maximum number of non-overlapping lectures. We will apply the earliest finish time algorithm step by step.

Step 1 is sorting by finish time. The sorted order becomes: A(1, 4), B(3, 5), C(0, 6), D(5, 7), E(3, 9), F(5, 9), G(6, 10), H(8, 11). Note that E and F both finish at 9; their relative order does not affect optimality, but for determinism we might order F(5, 9) before E(3, 9) if we sort by start time as a secondary key. For this walkthrough, we will keep the order as listed after primary sorting.

Step 2 is the greedy scan. We initialize last_finish = -infinity and an empty selected list. We examine A(1, 4): since 1 >= -infinity, we select A. selected = [A], last_finish = 4. Next, B(3, 5): 3 >= 4 is false, so B is skipped because it overlaps with A. Next, C(0, 6): 0 >= 4 is false, skipped. Next, D(5, 7): 5 >= 4 is true, so we select D. selected = [A, D], last_finish = 7. Next, E(3, 9): 3 >= 7 is false, skipped. F(5, 9): 5 >= 7 is false, skipped. G(6, 10): 6 >= 7 is false, skipped. Finally, H(8, 11): 8 >= 7 is true, so we select H. selected = [A, D, H], last_finish = 11. The algorithm terminates and returns 3 intervals.

Verification of Optimality

Is this result optimal? Could we have selected 4 intervals? Let us attempt to reason. Any feasible schedule can contain at most one interval from the overlapping cluster {A, B, C} since all three pairwise overlap. After picking one from that cluster, the next earliest finishing compatible interval is D, which blocks E, F, and G. Only H remains compatible after D. Thus 3 is indeed the maximum. If we had chosen C(0, 6) first (earliest start time heuristic), we would have selected C and then H for a total of only 2, which is suboptimal. If we had chosen the shortest interval B(3, 5) (duration 2), we would pick B, then D, then H for 3 as well in this case, but there exist other instances where shortest-first fails to achieve optimum.

This walkthrough highlights the importance of the sorted order. The algorithm never looks ahead; it simply commits to the earliest finishing compatible interval. The trace also shows how the algorithm naturally handles intervals that start exactly when another finishes, such as if we had an interval I(4, 5), it would be compatible with A(1, 4) and would be selected before B, demonstrating the half-open interval assumption.

Visual Trace Table

A tabular trace helps visualize the decision process. Each row shows the interval considered, its compatibility check, the action taken, and the state of the selected set. This format is particularly useful for debugging and for explaining the algorithm in interviews or documentation.

Complexity Analysis

The time and space complexity of interval scheduling maximization is dominated by the sorting step, making it highly efficient for large inputs. Understanding the complexity in best, average, and worst cases is crucial for predicting performance and for comparing this greedy solution with alternative approaches such as dynamic programming or brute force.

The algorithm consists of two distinct operations: sorting and scanning. Sorting n intervals by finish time using an optimal comparison-based sort requires O(n log n) time in all cases. The subsequent linear scan examines each interval exactly once, performing O(1) work per interval, for a total of O(n) time. Therefore, the overall time complexity is O(n log n) + O(n) = O(n log n). This holds for best, average, and worst cases because the sorting lower bound applies regardless of input distribution, and the scan is always linear. If intervals are already sorted by finish time, the scan alone is O(n), which is the best case for the overall procedure when sorting is not needed.

Space complexity is similarly efficient. The algorithm requires O(n) space to store the intervals and the sorted copy, plus O(k) space for the selected subset where k <= n. If sorting is done in-place, the extra space can be reduced to O(1) auxiliary space besides the input and output, or O(log n) due to recursion stack in some sort implementations. The scan itself uses only O(1) extra variables (last_finish, loop index). This makes the algorithm suitable for memory-constrained environments and for processing large datasets.

It is instructive to contrast this with the complexity of related problems. Weighted Interval Scheduling, where each interval has a value and we maximize total weight, cannot be solved by the same greedy strategy and requires O(n log n) time with dynamic programming plus binary search. Interval Partitioning, where we minimize the number of resources needed to schedule all intervals, also runs in O(n log n) but uses a priority queue. The unweighted maximization variant is thus among the most efficient scheduling problems.

The table above summarizes the complexity characteristics. Note that if finish times are bounded integers, such as times within a single day discretized to minutes, counting sort or radix sort could theoretically reduce sorting to O(n + k), yielding an overall O(n) algorithm. However, for general comparable finish times, O(n log n) is optimal due to the sorting lower bound. The linear scan's simplicity also means the constant factors are very small, making the algorithm fast in practice even for millions of intervals.

Variations and Optimizations

While the basic interval scheduling maximization problem has a clean greedy solution, numerous variations arise in practice that require different techniques or modest extensions. Understanding these variants is essential for recognizing when the simple EFT strategy applies and when a more sophisticated approach is needed.

The most famous variation is Weighted Interval Scheduling, where each interval i has an associated weight or value v(i), and the goal is to maximize the total weight of the selected compatible subset rather than the count. Here, the greedy EFT strategy fails. A classic counterexample is two intervals: a long interval with weight 100 that overlaps with two short intervals each of weight 60. EFT would pick the short intervals for total weight 120, which is better, but other arrangements can make EFT arbitrarily bad. The optimal solution for the weighted case uses dynamic programming after sorting by finish time, combined with binary search to find the latest compatible predecessor p(i) for each interval, achieving O(n log n) time.

Another important variant is Interval Partitioning (also called Interval Graph Coloring). Instead of maximizing the number of intervals scheduled on a single resource, we seek to schedule all intervals using the minimum number of resources (e.g., classrooms). This problem is solved by a different greedy strategy: sort intervals by start time and assign each interval to any available resource, or allocate a new resource if none is available. A priority queue tracking the earliest finishing time of each resource yields an O(n log n) solution, and the number of resources needed equals the maximum depth (maximum number of overlapping intervals at any point).

Additional optimizations and extensions include handling intervals with release times and deadlines, scheduling with k identical machines where we can schedule up to k overlapping intervals, and online interval scheduling where intervals arrive over time and decisions must be made without knowledge of future intervals. For the k-machine variant, a greedy algorithm using a min-heap of size k can maximize throughput. For online variants, no deterministic algorithm can be optimal, and competitive analysis is used to evaluate performance.

Optimization Techniques for Large Inputs

For very large n, micro-optimizations can matter. Using iterative sorting with key functions, avoiding object overhead by using tuples, and using local variables for last_finish can improve cache performance. If intervals are generated in sorted order (e.g., from a database query with ORDER BY finish_time), the O(n log n) sort can be skipped entirely. In distributed settings, intervals can be partitioned by time windows and scheduled independently with a merge step, though care must be taken to handle cross-partition overlaps.

# Weighted Interval Scheduling (DP) - for comparison
# This is NOT greedy; it shows why weighted case is different
def weighted_interval_scheduling(intervals):
    """
    intervals: list of (start, finish, weight)
    Returns max total weight using DP + binary search
    """
    if not intervals:
        return 0
    # Sort by finish time
    intervals_sorted = sorted(intervals, key=lambda x: x[1])
    n = len(intervals_sorted)
    starts = [x[0] for x in intervals_sorted]
    finishes = [x[1] for x in intervals_sorted]
    weights = [x[2] for x in intervals_sorted]

    # p[i] = largest index j < i such that finish[j] <= start[i]
    p = [-1] * n
    for i in range(n):
        # Binary search for latest compatible interval
        lo, hi = 0, i - 1
        best = -1
        while lo <= hi:
            mid = (lo + hi) // 2
            if finishes[mid] <= starts[i]:
                best = mid
                lo = mid + 1
            else:
                hi = mid - 1
        p[i] = best

    # DP: dp[i] = max weight for intervals 0..i
    dp = [0] * n
    dp[0] = weights[0]
    for i in range(1, n):
        include = weights[i] + (dp[p[i]] if p[i] != -1 else 0)
        exclude = dp[i-1]
        dp[i] = include if include > exclude else exclude

    return dp[n-1]

# Example where greedy by finish time fails for weighted case
weighted = [(1, 4, 10), (3, 5, 20), (0, 6, 100), (5, 7, 20)]
print(weighted_interval_scheduling(weighted))  # 40 (picks (3,5) + (5,7)), not 100

Real-World Applications

Interval scheduling maximization is far from a purely academic exercise; it models a wide range of real-world resource allocation problems where a single reusable resource must be shared efficiently. Any scenario involving a single machine, room, or channel that can handle only one job at a time and where jobs have fixed time windows can be framed as an interval scheduling problem.

In operating systems and cloud computing, CPU scheduling and job dispatching often involve selecting the maximum number of non-overlapping tasks to maximize throughput. While modern schedulers consider priorities and deadlines, the core principle of freeing the resource as early as possible to accommodate more tasks is directly derived from interval scheduling. Similarly, in high-performance computing clusters, batch schedulers use interval scheduling to pack as many jobs as possible onto a limited set of nodes when jobs have specified start and end times.

Web servers and databases provide another rich application domain. A web server handling persistent connections or a database managing locks on a single table row must decide which requests to serve to maximize the number of satisfied clients without overlapping access. Content delivery networks (CDNs) scheduling cache updates or video streaming servers allocating bandwidth for fixed-duration streams also benefit from maximizing the number of compatible intervals. In network routing, scheduling transmissions on a single frequency channel to avoid collisions is an interval scheduling problem where each transmission is an interval and overlapping transmissions would interfere.

Beyond computing, the problem appears in everyday logistics. Classroom and conference room assignment for a single room, interview scheduling for a single interviewer, and even telescope observation scheduling where each observation requires exclusive use of the instrument for a specific window all map directly to interval scheduling maximization. In bioinformatics, selecting the maximum number of non-overlapping genetic segments or aligning sequences can be modeled similarly.

The table above illustrates how the abstract interval model translates across domains. In each case, the greedy EFT algorithm provides an optimal, fast solution when all intervals are equally valuable. When intervals have different priorities, the weighted variant or more complex scheduling with fairness constraints may be needed, but the unweighted solution often serves as a baseline or subroutine within larger optimization frameworks.

Comparison with Alternatives

Choosing the right scheduling strategy depends on the objective and constraints. Interval scheduling maximization is one point in a spectrum of scheduling problems, and comparing it with alternative approaches clarifies when EFT is appropriate and when other methods are required. The key distinction is whether the goal is to maximize count, minimize resources, maximize weight, or handle online arrivals.

The most common alternatives are other greedy heuristics that seem plausible but are not optimal for maximizing count. Earliest Start Time (EST) sorts by start time and picks the earliest starting compatible interval. Shortest Processing Time (SPT) sorts by duration (f - s) and picks the shortest compatible interval. Fewest Conflicts sorts by the number of overlapping intervals and picks the interval that conflicts with the fewest others. All three can be shown to be suboptimal with simple counterexamples, yet they are sometimes confused with the correct EFT approach, especially by those new to greedy algorithms.

Dynamic Programming (DP) is the correct alternative for the weighted case. It guarantees optimality for weighted intervals but requires O(n log n) time and O(n) space, and is more complex to implement. Brute force enumeration is optimal but exponential and only feasible for very small n, serving mainly as a baseline for testing correctness on small inputs. For interval partitioning, the greedy algorithm using a priority queue is optimal for minimizing the number of resources, which is a different objective altogether.

As the comparison shows, EFT is the clear winner for the unweighted maximization objective due to its combination of optimality, efficiency, and simplicity. The other greedy heuristics should be avoided for this objective, though they may be useful for different objectives (e.g., SPT is optimal for minimizing average waiting time in some scheduling contexts). DP is the necessary upgrade when intervals have differing values, and brute force is only a theoretical tool. Understanding these trade-offs ensures that the right algorithm is applied to the right problem, avoiding both suboptimal solutions and unnecessary complexity.

Common Mistakes and Best Practices

Even though the algorithm is simple, practitioners and students frequently make mistakes that lead to incorrect or inefficient implementations. Recognizing these pitfalls and adopting best practices is crucial for writing correct, maintainable, and performant code.

A common mistake is sorting by the wrong key. Sorting by start time or by duration instead of finish time is the most frequent error and leads to suboptimal results that may pass simple tests but fail on adversarial inputs. Another subtle mistake is mishandling the compatibility condition. Using s > last_finish (strictly greater) instead of s >= last_finish incorrectly disallows back-to-back intervals where one finishes exactly when another starts, reducing the achievable count. Conversely, using s >= last_finish when intervals are defined as closed and cannot share endpoints would incorrectly allow overlapping intervals. Clarifying the interval model upfront avoids this confusion.

Edge cases are another source of bugs. Empty input, single interval, intervals with identical finish times, zero-length intervals (s == f), and intervals with negative times must all be handled. Failing to handle an empty list can cause index errors if the code assumes at least one interval. Not breaking ties deterministically can lead to non-reproducible results, which is problematic for testing and debugging. Additionally, mutating the input list by sorting in-place without making a copy can cause unexpected side effects for the caller.

Best practices include always validating input, making a copy before sorting if the original order must be preserved, using a stable sort with a secondary key for determinism, and writing clear, commented code that states the invariant (last_finish is the finish time of the last selected interval). Testing should include brute-force verification on small random inputs to ensure correctness, as well as performance tests on large inputs. For production code, consider using dataclasses or named tuples for clarity, and provide both count-only and full-schedule variants to give callers flexibility. Finally, document the time and space complexity and the assumption that intervals are half-open, so future maintainers understand the contract.

Checklist for Robust Implementation

• Sort by finish time, not start time or duration; use key=lambda x: (x[1], x[0]) for tie-breaking.
• Use s >= last_finish for half-open intervals; adjust to s > last_finish only if closed intervals are required.
• Handle empty input, single interval, and duplicate finish times explicitly.
• Validate intervals (s <= f) and raise informative errors for invalid data.
• Do not mutate the caller's list; sort a copy or document in-place behavior.
• Test against brute force for n <= 10 with random intervals to verify optimality.

Interview Questions

Interval scheduling maximization is a staple of technical interviews because it tests understanding of greedy algorithms, proof techniques, and implementation details. Below are common interview questions with guidance on how to approach them effectively.

Question 1: Why does earliest finish time work while earliest start time does not? Provide a counterexample.

This question tests conceptual understanding. A strong answer explains the intuition that earliest finish time leaves maximal room for remaining intervals, then provides a concrete counterexample for earliest start time. For example, intervals [(0, 10), (1, 2), (2, 3), (3, 4)] — earliest start time picks (0, 10) and gets 1 interval, while EFT picks (1, 2), (2, 3), (3, 4) for 3 intervals. Discuss how the exchange argument proves EFT's optimality and why EST lacks the greedy-choice property. Mention that EST can be arbitrarily bad, with a performance ratio approaching 0 as n grows.

Question 2: Implement interval scheduling maximization and analyze its complexity. How would you handle intervals that are already sorted?

Interviewers expect clean code with O(n log n) sorting and O(n) scanning, plus handling of edge cases. Write the basic function, explain that sorting dominates, and note that if intervals are already sorted by finish time, the algorithm runs in O(n) time and O(1) extra space. Discuss in-place vs. copy sorting, stability, and tie-breaking. Be prepared to walk through an example and to test with empty input and overlapping intervals. Bonus points for mentioning that Python's sorted is stable and uses Timsort.

Question 3: How would you extend the solution to Weighted Interval Scheduling where each interval has a value?

This question checks whether you know the limits of greedy. Explain that EFT is no longer optimal for weighted intervals and provide a counterexample where a high-weight long interval should be skipped in favor of multiple lower-weight intervals or vice versa. Describe the DP solution: sort by finish time, compute p(i) via binary search, define dp[i] = max(dp[i-1], v(i) + dp[p(i)]), and reconstruct the solution by backtracking. State the O(n log n) time and O(n) space complexity, and contrast it with the unweighted greedy approach.

Question 4: Given intervals, find the minimum number of rooms needed to schedule all intervals (Interval Partitioning). How does this differ from maximization?

This variant tests ability to distinguish related problems. Explain that maximization selects the largest subset for one resource, while partitioning schedules all intervals using the fewest resources. Describe the greedy algorithm for partitioning: sort by start time, use a min-heap keyed by finish time to track room availability, allocate a new room if no room is free (heap top > current start), otherwise reuse the room that frees earliest. State that the number of rooms needed equals the maximum depth of overlap, and that the algorithm runs in O(n log n) time. Highlight that the objectives and greedy choices are fundamentally different.

Question 5: Can you prove that the greedy EFT algorithm is optimal? Sketch the exchange argument.

Proof questions evaluate rigorous reasoning. Outline the proof: let GREEDY be the greedy solution and OPT be an optimal solution. Show by induction that after k steps, GREEDY's k-th finish time is <= OPT's k-th finish time (greedy stays ahead). Then use an exchange argument: let i1 be the earliest finishing interval; there exists an optimal solution containing i1, because if OPT's first interval j != i1, replace j with i1 (since f(i1) <= f(j), compatibility is preserved and size unchanged). Apply induction to the subproblem of intervals compatible with i1. Conclude GREEDY is optimal and has maximum cardinality. Mention that this proof fails for weighted case because exchange may reduce total weight.