Solving Interval Scheduling Problems with Sorting and Invariants

Welcome. This first module builds the interview patterns that recur in backend/SDE coding rounds: recognize the problem structure, identify the right data structure or ordering, state an invariant, and justify complexity clearly.

This lesson introduces the interval frontier pattern. You will solve the classic “maximum number of non-overlapping activities” problem with a greedy sort, explain why the choice is optimal, and distinguish it from the closely related merge intervals pattern. By the end, you should be able to write and defend the solution in Java rather than merely recognize it from LeetCode.

Study time: about 40–45 minutes.

---

1. Identify the exact interval problem

An interval is a pair $(s_i,f_i)$, where $s_i$ is a start time and $f_i$ is a finish time.

For activity selection (also called maximum non-overlapping intervals or maximum meetings in one room):

• Input: activities with start and finish times.
• Constraint: chosen activities must not overlap.
• Goal: choose the largest possible number of compatible activities.

In the usual convention, an activity ending exactly when another starts is compatible:

$$f_i\le s_j$$

So $[1,3]$ and $[3,5]$ can both be selected. Always check the problem statement: some domains treat shared endpoints differently.

A common interview failure is solving the wrong optimization problem. These superficially similar prompts require different approaches:

Prompt	Goal	Core idea
“Maximum meetings in one room”	Maximize number selected	Sort by finish time; greedy
“Merge all overlapping intervals”	Return union of ranges	Sort by start time; maintain merged frontier
“Minimum meeting rooms”	Minimize number of concurrent rooms	Sort plus a min-heap
“Maximum total value of non-overlapping jobs”	Maximize weighted profit	Dynamic programming, not this greedy rule

This lesson covers the first two. The min-heap variant comes next.

---

2. Activity selection: finish early to preserve options

Suppose a service has one deployment window and several non-overlapping maintenance jobs have been proposed. If your objective is to run as many jobs as possible, choosing a job that finishes earliest is safest: it leaves the largest remaining window for later jobs.

The greedy strategy is:

1. Sort activities by increasing finish time.
2. Select the first activity.
3. Scan the rest in that order.
4. Select an activity only when its start time is at least the finish time of the most recently selected activity.

The crucial choice is finish time, not start time and not duration.

Why tempting alternatives fail

Earliest start time can select a long activity that blocks many short ones.

• $[0,10]$
• $[1,2]$
• $[2,3]$
• $[3,4]$

Picking the earliest-starting interval yields only one activity. Skipping it permits three.

Shortest duration is also unsafe.

• $[0,4]$
• $[3,5]$
• $[4,8]$

The shortest activity is $[3,5]$, but selecting it blocks both other intervals. The optimal selection is $[0,4]$ and $[4,8]$.

The greedy choice must be justified by what it preserves. An earliest finishing activity leaves every activity beginning after its finish still available. No other local rule gives that guarantee.

Java implementation

A record keeps the original identifier attached to each interval. This matters when the interviewer asks you to return selected meeting IDs rather than only the count.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

record Activity(int id, int start, int finish) { }

public class ActivitySelector {

    static List<Activity> selectMaximumActivities(List<Activity> activities) {
        List<Activity> sorted = new ArrayList<>(activities);

        sorted.sort(
            Comparator.comparingInt(Activity::finish)
                      .thenComparingInt(Activity::start)
        );

        List<Activity> selected = new ArrayList<>();
        int lastFinish = Integer.MIN_VALUE;

        for (Activity activity : sorted) {
            if (activity.start() >= lastFinish) {
                selected.add(activity);
                lastFinish = activity.finish();
            }
        }

        return selected;
    }
}

The tie-breaker by start time is optional for correctness. It makes the result deterministic, which is useful in tests and production code.

Notice what the loop does not do: it does not compare the current activity against every previously selected activity. That would be unnecessarily expensive.

---

3. The loop invariant: why one boundary is enough

A loop invariant is a statement that remains true before and after every iteration. In an interview, naming the invariant often turns a code explanation into a correctness argument.

For the activity-selection loop, maintain:

Invariant: selected contains only mutually compatible activities, and lastFinish equals the finish time of the most recently selected activity. Because activities are processed in nondecreasing finish-time order, this is also the greatest finish time among selected activities.

When considering a candidate activity $j$, the test is:

$$s_j\ge f_{\text{last}}$$

If it passes, it is compatible with the last selected activity. It is therefore compatible with every earlier selected activity as well, because each earlier one finished no later than the last one:

$$f_i\le f_{\text{last}}\le s_j$$

Maintaining the invariant

• Initialization: selected is empty and lastFinish is effectively negative infinity. In Java, Integer.MIN_VALUE serves if time values are ordinary int values.
• When an activity is selected: its start satisfies the compatibility condition. Update lastFinish to its finish time. Since the input is sorted by finish time, this new value is at least every previous selected finish.
• When an activity is skipped: neither selected nor lastFinish changes, so the invariant remains true.

This proves the algorithm always returns a valid schedule. Validity alone does not prove it returns the largest one. For that, we need the greedy-choice argument.

Why earliest finish is optimal: the exchange argument

Let $G$ be the first activity chosen by the greedy algorithm. Since it has the earliest finish time, it finishes no later than the first activity $O$ selected by any optimal solution:

$$f_G\le f_O$$

Take an optimal solution that begins with $O$. Replace $O$ with $G$.

This replacement remains feasible: every later activity in that optimal solution starts at or after $f_O$, and $G$ finishes no later than $O$. Therefore, those later activities are also compatible with $G$. The replacement does not change the number of activities selected.

So there exists an optimal solution whose first activity is exactly the greedy choice. After fixing that choice, the remaining problem is the same activity-selection problem restricted to intervals that start at or after $f_G$. The same logic applies again. Repeating this reasoning shows that greedy can be extended into an optimal solution, one choice at a time.

A concise interview version is:

“I sort by finish time and take every compatible interval. The invariant is that lastFinish is the latest finish of my selected schedule, so checking only that value guarantees compatibility. For optimality, an exchange argument shows that any optimal schedule can replace its first activity with the greedy earliest-finishing one without reducing its size. The same argument applies recursively to the remaining compatible activities.”

Time and space complexity

For $n$ activities:

• Sorting costs $O(n\log n)$.
• The scan costs $O(n)$.
• Total time is:

$$O(n\log n)$$

Sorting dominates the linear scan.

The returned list can contain $O(n)$ activities. This implementation also copies the input before sorting; Java’s object-array sorting may use additional memory internally. In an interview, the safe answer is: $O(n\log n)$ time and $O(n)$ space including the output and copied list.

---

4. A sibling pattern: merge intervals

The activity-selection problem discards conflicting intervals because the goal is maximum count. In merge intervals, you keep all input information but coalesce overlaps into their union.

For example:

$$[1,3],[2,6],[8,10],[15,18]$$

becomes:

$$[1,6],[8,10],[15,18]$$

The sorting key changes:

• Activity selection sorts by finish time because it wants to leave future capacity.
• Merge intervals sorts by start time because it wants to walk left to right and discover overlaps with the current combined range.

Merge invariant

After processing any prefix of intervals sorted by start time:

Invariant: merged is a sorted list of pairwise-disjoint intervals representing exactly the union of all processed input intervals.

When processing the next interval:

• If it begins after the end of the last merged interval, it is disjoint, so append it.
• Otherwise, it overlaps the active frontier, so extend the last merged interval’s end to the larger of the two end values.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class IntervalMerger {

    static int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][];
        }

        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));

        List<int[]> merged = new ArrayList<>();

        for (int[] interval : intervals) {
            if (merged.isEmpty()) {
                merged.add(new int[] {interval[0], interval[1]});
                continue;
            }

            int[] last = merged.get(merged.size() - 1);

            // Touching intervals are merged under this specification.
            if (interval[0] <= last[1]) {
                last[1] = Math.max(last[1], interval[1]);
            } else {
                merged.add(new int[] {interval[0], interval[1]});
            }
        }

        return merged.toArray(new int[merged.size()][]);
    }
}

The Math.max is essential for nested intervals. If the current merged interval is $[1,8]$ and the next is $[2,4]$, the result must remain $[1,8]$, not shrink to $[1,4]$.

The same time analysis applies:

$$O(n\log n)+O(n)=O(n\log n)$$

A useful distinction about endpoints:

Problem semantics	Test for overlap or compatibility
Activity selection, touching allowed	select if start >= lastFinish
Activity selection, touching forbidden	select if start > lastFinish
Merge intervals, touching merged	merge if start <= lastEnd
Merge intervals, touching separate	merge if start < lastEnd

Do not memorize only an operator. First state the interval semantics, then choose the operator that implements it.

---

5. A compact interview workflow

When you see intervals in a coding problem, use this sequence:

1. State the objective. Are you selecting, merging, allocating rooms, or maximizing weighted value?
2. Choose the sort key from the objective. Finish time preserves capacity; start time supports a left-to-right sweep.
3. Name the frontier state. For this lesson, it is either lastFinish or the last merged interval.
4. State the invariant. Explain what your processed prefix and frontier represent.
5. Implement the scan. Each interval should require constant-time work after sorting.
6. Give complexity. Sorting usually dominates with $O(n\log n)$.
7. Clarify endpoint behavior. Ask whether adjacent intervals conflict or merge.

This is more reliable than pattern matching on a familiar title. “Meetings,” “CPU jobs,” “maintenance windows,” “calendar bookings,” and “network reservation periods” can all reduce to intervals, but their objective determines the algorithm.

---

Key takeaways

• For maximum non-overlapping activities, sort by earliest finish time and select every compatible interval.
• The scheduling invariant is that lastFinish represents the latest finish time in the selected schedule; sorted finish times make one comparison sufficient.
• The earliest-finish rule is optimal by an exchange argument: it can replace the first activity of an optimal schedule without making later choices infeasible.
• The runtime is $O(n\log n)$, dominated by sorting.
• Merge intervals is related but different: sort by start time and maintain the rightmost endpoint of the active merged interval.
• Endpoint equality is a specification decision, not a detail to guess.

Next, you will move from a single scheduling frontier to many concurrent frontiers: using heaps for top-$k$ and priority-scheduling problems, including the “minimum meeting rooms” family.