Interval Patterns

1. Introduction: Managing Time and Space

Imagine you are building the calendar app for Google. Users schedule meetings with a [start, end] time. If a user tries to book three meetings that happen at the same time, the calendar needs to flag a conflict. If a user wants to know their total hours worked, the calendar needs to merge overlapping blocks of time.

This represents the Interval Pattern, a sub-category of Greedy Algorithms. An Interval is just a 1D line segment defined by a start point and an end point. Almost every major tech company uses Interval problems in interviews because they test your ability to sort custom objects, manage overlapping states, and handle edge cases (like intervals touching exactly at their boundaries).

2. Core Concept: The Universal First Step

For 95% of Interval problems, the very first step is exactly the same: Sort the intervals based on their Start Time.

Why? Because if the intervals are sorted by start time, we mathematically guarantee that when we look at interval[i] and interval[i+1], the start of i happens before (or at the same time as) the start of i+1. This reduces the complex 2D geometry of overlapping lines into a simple 1D check: "Does the start of the next interval happen BEFORE the end of my current interval?"

The Overlap Check: If A comes before B (because we sorted by start time), they overlap IF AND ONLY IF: B.start <= A.end

3. Beginner Code Example: Merge Intervals

Problem Statement: (LeetCode 56) Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

The Insight: Sort by start time. Create an active currentInterval. Iterate through the list. If the next interval overlaps, stretch the currentInterval's end time to encompass it. If it doesn't overlap, save currentInterval to the results and start a new one.

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

public class MergeIntervals {
    public static int[][] merge(int[][] intervals) {
        if (intervals.length <= 1) return intervals;
        
        // 1. Sort by Start Time
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        
        List<int[]> result = new ArrayList<>();
        
        // Initialize the first active interval
        int[] currentInterval = intervals[0];
        result.add(currentInterval); // Add to result by reference!
        
        for (int[] nextInterval : intervals) {
            int currentEnd = currentInterval[1];
            int nextStart = nextInterval[0];
            int nextEnd = nextInterval[1];
            
            // Overlap check
            if (nextStart <= currentEnd) {
                // Merge them by updating the end of the current interval
                // We must use Math.max because the next interval might be completely INSIDE the current one!
                currentInterval[1] = Math.max(currentEnd, nextEnd);
            } else {
                // No overlap. Start a new active interval.
                currentInterval = nextInterval;
                result.add(currentInterval);
            }
        }
        
        // Convert List to 2D Array
        return result.toArray(new int[result.size()][]);
    }
}

Complexity Analysis:

• Time Complexity: $O(N \log N)$ for the sorting step. The merge pass is $O(N)$.
• Space Complexity: $O(N)$ for the result list.

4. Intermediate Code Example: Insert Interval

Problem Statement: (LeetCode 57) You are given an array of non-overlapping intervals intervals sorted by start time, and a newInterval. Insert newInterval so the list remains sorted and non-overlapping.

The Insight: We could just add it to the list, resort the whole thing ($O(N \log N)$), and run the Merge Intervals algorithm. But the interviewer wants $O(N)$! Since it's already sorted, we can do it in 3 distinct linear phases:

1. Add all intervals that end before the new interval starts.
2. Merge all intervals that overlap with the new interval.
3. Add all remaining intervals.

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

public class InsertInterval {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> result = new ArrayList<>();
        int i = 0;
        int n = intervals.length;
        
        // Phase 1: Add all intervals completely BEFORE the new interval
        while (i < n && intervals[i][1] < newInterval[0]) {
            result.add(intervals[i]);
            i++;
        }
        
        // Phase 2: Merge all overlapping intervals into the newInterval
        // They overlap if the current interval starts BEFORE the newInterval ends
        while (i < n && intervals[i][0] <= newInterval[1]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        result.add(newInterval); // Add the massive merged interval
        
        // Phase 3: Add the rest
        while (i < n) {
            result.add(intervals[i]);
            i++;
        }
        
        return result.toArray(new int[result.size()][]);
    }
}

5. Advanced Code Example: Non-Overlapping Intervals

Problem Statement: (LeetCode 435) Given an array of intervals, return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

This is the exact same logic as the "Activity Selection" problem from the Greedy Basics section. We want to KEEP the maximum number of non-overlapping intervals. Total - Max Kept = Min Removed.

The Warning Trick: Usually we sort by start time. But if we want to maximize the number of intervals we keep, we MUST sort by End Time. Why? Because an interval that ends incredibly early leaves the maximum amount of space for other intervals!

import java.util.Arrays;

public class EraseOverlap {
    public int eraseOverlapIntervals(int[][] intervals) {
        if (intervals.length == 0) return 0;
        
        // CRITICAL: Sort by END TIME, not start time!
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
        
        int keepCount = 1;
        int lastEndTime = intervals[0][1];
        
        for (int i = 1; i < intervals.length; i++) {
            int currentStart = intervals[i][0];
            
            // If it starts after or when the last one ended, we can keep it!
            if (currentStart >= lastEndTime) {
                keepCount++;
                lastEndTime = intervals[i][1];
            }
        }
        
        // We want the number to REMOVE, not keep.
        return intervals.length - keepCount;
    }
}

Complexity Analysis:

• Time Complexity: $O(N \log N)$ for sorting.
• Space Complexity: $O(1)$.

6. Common Mistakes Beginners Make

1. Confusing < and <= for overlaps

   • The Mistake: Using < when checking overlaps, e.g., if (nextStart < currentEnd).
   • Why it's wrong: You must read the problem description carefully. Does [1, 4] and [4, 5] overlap? In most problems, boundaries touching is NOT considered an overlap, meaning they can be merged into [1, 5]. If you use strict <, you will fail to merge touching intervals.

2. Always sorting by Start Time implicitly

   • The Mistake: Sorting by Start Time for LeetCode 435 (Erase Overlapping).
   • Why it's wrong: If you have [1, 100], [2, 3], [4, 5]. Sorting by start time evaluates [1, 100] first. You keep it, and are forced to delete the other two. But the optimal answer is to delete [1, 100] and keep the two small ones! Sorting by End Time guarantees you evaluate [2, 3] first.

3. Integer Overflow in custom Comparators

   • The Mistake: Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
   • Why it's wrong: If a[0] is a massive negative number and b[0] is a massive positive number, subtracting them will overflow the 32-bit Integer limit, returning a mathematically incorrect sign and breaking the sort.
   • The Fix: Always use Integer.compare(a[0], b[0]).

7. Interview Q&A

Q1: What is the "Sweepline" Algorithm? Answer: It is an advanced interval pattern (often used for Meeting Rooms II). Instead of treating [start, end] as a single object, you separate them into two independent "events": (start, +1) and (end, -1). You sort all events by time. You then iterate through the timeline, adding the values. The maximum running sum at any point is the maximum number of overlapping intervals!

Q2: How do you handle intervals where the start and end times are not integers, but Dates or Timestamps? Answer: In Java, you parse them into Unix Epoch Time (a long representing milliseconds since 1970). Once they are longs, the exact same interval math applies.

Q3: Can Interval problems be solved without sorting? Answer: Usually not, which means $O(N \log N)$ is the theoretical limit. However, if the interval times are bounded to a very small range (e.g., hours in a day, 0 to 24), you can use a fixed-size array as a bucket/timeline and do it in $O(N)$ time (Bucket Sort concept).

8. Practice Problems

1. Merge Intervals (LeetCode 56)
   • Goal: Master the foundation.
2. Meeting Rooms II (LeetCode 253 / Premium)
   • Hint: Master the Sweepline / Priority Queue approach to find maximum concurrent overlaps.
3. Minimum Number of Arrows to Burst Balloons (LeetCode 452)
   • Hint: Identical to Non-Overlapping Intervals. Sort by End Time!

9. Summary

• The Golden Rule: Start by sorting the array. (By Start Time for merging, by End Time for finding disjoint sets).
• The Overlap Check: If sorted by start time, A and B overlap if B.start <= A.end.
• Merge Math: When merging, the new end time is ALWAYS max(A.end, B.end), because one interval might completely engulf the other.
• Phases: If the array is already sorted, don't resort. Use the 3-phase while loop to achieve $O(N)$ insertion.