Advanced Interval Patterns

Once you've mastered merging intervals, you can apply it to solve more complex questions. We'll explore three such patterns in this chapter:

1. Chronological Ordering (Sweep-Line): Counting concurrent events.
2. Finding Intersections: Identifying overlapping periods between multiple lists of intervals.
3. Identifying Gaps: Locating the "free time" or non-covered periods.

1. Chronological Ordering (Sweep-Line)

This pattern is for resource allocation or "how many things are happening at once" problems.

At a busy airport, how many gates do you need to ensure no plane is kept waiting on the tarmac?

Each plane's time on the ground is an interval. We need to find the peak number of planes at the gates simultaneously.

Problem: Meeting Rooms II (LeetCode Link): Given an array of meeting time intervals, find the minimum number of conference rooms required. 💡 HintInstead of tracking intervals, track the individual start and end events. What happens to your room count when a meeting starts vs. when one ends?

Events, Not Intervals

The insight is to deconstruct the intervals into individual "events" (start and end points) and process them in chronological order.

Let's take [[0, 30], [5, 10], [15, 20]].

• Events:
  • +1 at time 0 (meeting starts)
  • +1 at time 5 (meeting starts)
  • -1 at time 10 (meeting ends)
  • +1 at time 15 (meeting starts)
  • -1 at time 20 (meeting ends)
  • -1 at time 30 (meeting ends)

By processing these events in order, we can track the number of active rooms:

• t=0: rooms = 1
• t=5: rooms = 2 (This is our peak)
• t=10: rooms = 1
• t=15: rooms = 2
• t=20: rooms = 1
• t=30: rooms = 0

The maximum value reached (2) is the answer. This is called a sweep-line algorithm.

Two Ways to Implement Sweep-Line

There are two common ways to implement this logic. The first is a direct translation of the event-list idea. The second is a more optimized approach using a min-heap, which is often preferred in interviews.

Method 1: The Event List (Direct Implementation)

You can create a single list of all start and end points, sort it, and iterate through it.

1. Create a list of (time, type) tuples. type is +1 for a start and -1 for an end.
2. Sort this list. A key detail is that if a start and end time are the same, you must process the start first.
3. Iterate through the sorted events, maintaining a current_rooms counter and a max_rooms tracker.

This method perfectly matches the conceptual model but can be slightly more complex to code correctly due to the custom sorting logic.

Method 2: The Min-Heap (Optimized Implementation)

A min-heap provides a more elegant and efficient way to solve this. The heap will store the end times of all meetings currently in progress. This way, you can instantly know when the next meeting is scheduled to end.

1. Sort intervals by their start time. This ensures we process meetings in the order they begin.
2. Initialize a min-heap and add the end time of the first meeting. The size of the heap will represent the number of rooms currently in use.
3. Iterate through the rest of the meetings:
   • Check the meeting at the top of the heap—this is the one that ends the soonest.
   • If the current meeting starts after or at the same time as the earliest meeting ends (current.start >= heap.top()), it means a room has freed up. We can reuse it, so we pop from the heap.
   • Regardless, the current meeting now needs a room, so we push its end time onto the heap.
4. The maximum size the heap reaches during this process is the minimum number of rooms required.

def minMeetingRooms(intervals):
    if not intervals:
        return 0
    intervals.sort(key=lambda x: x[0])
    rooms = []
    heapq.heappush(rooms, intervals[0][1])
    for i in range(1, len(intervals)):
        if intervals[i][0] >= rooms[0]:
            heapq.heappop(rooms)
        heapq.heappush(rooms, intervals[i][1])
    return len(rooms)

public int minMeetingRooms(int[][] intervals) {
    if (intervals == null || intervals.length == 0) return 0;
    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
    PriorityQueue<Integer> rooms = new PriorityQueue<>();
    rooms.add(intervals[0][1]);
    for (int i = 1; i < intervals.length; i++) {
        //If the room with earliest end time is free now, assign it to the current meeting
        if (intervals[i][0] >= rooms.peek()) {
            rooms.poll();
        }
        
        rooms.add(intervals[i][1]);
    }
    return rooms.size();
}

int minMeetingRooms(std::vector<std::vector<int>>& intervals) {
    if (intervals.empty()) return 0;
    std::sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) { return a[0] < b[0]; });
    std::priority_queue<int, std::vector<int>, std::greater<int>> rooms;
    rooms.push(intervals[0][1]);
    for (size_t i = 1; i < intervals.size(); ++i) {
        if (intervals[i][0] >= rooms.top()) {
            rooms.pop();
        }
        rooms.push(intervals[i][1]);
    }
    return rooms.size();
}

2. Finding Intersections

This pattern is used when you have two (or more) lists of intervals and you need to find their common, overlapping periods. As always, try this problem first:

Problem: Interval List Intersections (LeetCode Link): You are given two lists of closed intervals, firstList and secondList. Each list of intervals is pairwise disjoint and in sorted order. Return the intersection of these two interval lists. 💡 HintUse two pointers, one for each list. How do you calculate the overlap between two intervals?

Two-Pointer Merge

As with any other merge interval problem, the key is to leverage the fact that both lists are sorted. Now combine this with a two-pointer approach, similar to the merge step in merge sort.

1. Initialize two pointers, i for firstList and j for secondList.
2. While both pointers are within the bounds of their lists:
   • Let intervalA = firstList[i] and intervalB = secondList[j].
   • Calculate the potential intersection:
     • intersection_start = max(intervalA.start, intervalB.start)
     • intersection_end = min(intervalA.end, intervalB.end)
   • If intersection_start <= intersection_end, a valid, non-empty intersection exists. Add [intersection_start, intersection_end] to your result.
   • Now, advance one of the pointers. Which one? The one whose interval ends first. This is because that interval cannot possibly overlap with any subsequent intervals in the other list.
     • If intervalA.end < intervalB.end, increment i.
     • Otherwise, increment j.
3. Return the list of intersections.

def intervalIntersection(firstList, secondList):
    i, j = 0, 0
    result = []
    while i < len(firstList) and j < len(secondList):
        start = max(firstList[i][0], secondList[j][0])
        end = min(firstList[i][1], secondList[j][1])
        if start <= end:
            result.append([start, end])
        if firstList[i][1] < secondList[j][1]:
            i += 1
        else:
            j += 1
    return result

public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
    List<int[]> result = new ArrayList<>();
    int i = 0, j = 0;
    while (i < firstList.length && j < secondList.length) {
        int start = Math.max(firstList[i][0], secondList[j][0]);
        int end = Math.min(firstList[i][1], secondList[j][1]);
        if (start <= end) {
            result.add(new int[]{start, end});
        }
        if (firstList[i][1] < secondList[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    return result.toArray(new int[result.size()][]);
}

std::vector<std::vector<int>> intervalIntersection(std::vector<std::vector<int>>& firstList, std::vector<std::vector<int>>& secondList) {
    std::vector<std::vector<int>> result;
    int i = 0, j = 0;
    while (i < firstList.size() && j < secondList.size()) {
        int start = std::max(firstList[i][0], secondList[j][0]);
        int end = std::min(firstList[i][1], secondList[j][1]);
        if (start <= end) {
            result.push_back({start, end});
        }
        if (firstList[i][1] < secondList[j][1]) {
            i++;
        } else {
            j++;
        }
    }
    return result;
}

3. Identifying Gaps

This pattern is about finding the empty spaces between a set of intervals. Try this problem, this is a hard leetcode problem, but if you came so far in our lesson you should be able to solve it.

Problem: Employee Free Time (LeetCode Link): You are given a list of schedules for several employees. Find the list of finite intervals representing the common free time for all employees. 💡 HintFirst, combine all meetings into one list. Then, what does a merged list of all busy times tell you about the free times?

Merge and Find Gaps

Conceptually, the easiest way to think about this is to first merge all the busy-time intervals into a single, consolidated list of non-overlapping busy periods. Then, you can simply find the time between the end of one busy period and the start of the next.

1. Flatten: Combine all intervals from all employees into a single list.
2. Sort: Sort this flattened list by start time.
3. Merge: Use the basic "Merge Intervals" pattern from the previous chapter to create a consolidated list of all busy times.
4. Find Gaps: Iterate through the merged busy-time intervals. The free time is the gap between the end of one interval and the start of the next.
   • For merged_intervals = [[8, 12], [13, 15], [17, 19]]
   • The first gap is between 12 (end of the first) and 13 (start of the second). So, [12, 13] is a free interval.
   • The second gap is between 15 and 17. So, [15, 17] is a free interval.

Optimization: No Need to Explicitly Merge

If you think about it, we don't actually need to build a new list of merged intervals (step 3). We only need to know one thing: the maximum end time we saw before the current time. By just tracking that single variable, we can find the gaps in a single pass right after sorting.

def employeeFreeTime(schedule):
    # 1. Flatten
    all_intervals = [iv for emp_sched in schedule for iv in emp_sched]
    # 2. Sort
    all_intervals.sort(key=lambda x: x[0])
    
    if not all_intervals:
        return []

    # 3. Loop and Find Gaps
    gaps = []
    last_end = all_intervals[0][1]
    
    for i in range(1, len(all_intervals)):
        current_start, current_end = all_intervals[i]
        # If there's a gap
        if current_start > last_end:
            gaps.append([last_end, current_start])
        # Update the last seen end time
        last_end = max(last_end, current_end)
            
    return gaps

public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
    // 1. Flatten
    List<Interval> allIntervals = new ArrayList<>();
    for (List<Interval> empSched : schedule) {
        allIntervals.addAll(empSched);
    }

    if (allIntervals.isEmpty()) {
        return Collections.emptyList();
    }

    // 2. Sort
    Collections.sort(allIntervals, (a, b) -> a.start - b.start);
    

    // 3. Loop and Find Gaps
    List<Interval> result = new ArrayList<>();
    int lastEnd = allIntervals.get(0).end;
    for (int i = 1; i < allIntervals.size(); i++) {
        Interval current = allIntervals.get(i);
        // If there's a gap
        if (current.start > lastEnd) {
            result.add(new Interval(lastEnd, current.start));
        }
        // Update the last seen end time
        lastEnd = Math.max(lastEnd, current.end);
    }
    return result;
}

// Definition for an Interval.
// public class Interval {
//     public int start;
//     public int end;
//     ...
// };

std::vector<Interval> employeeFreeTime(std::vector<std::vector<Interval>>& schedule) {
    // 1. Flatten
    std::vector<Interval> all_intervals;
    for (const auto& emp_sched : schedule) {
        all_intervals.insert(all_intervals.end(), emp_sched.begin(), emp_sched.end());
    }

    if (all_intervals.empty()) {
        return {};
    }

    // 2. Sort
    std::sort(all_intervals.begin(), all_intervals.end(), [](const Interval& a, const Interval& b) {
        return a.start < b.start;
    });

    // 3. Loop and Find Gaps
    std::vector<Interval> result;
    int last_end = all_intervals[0].end;
    for (size_t i = 1; i < all_intervals.size(); ++i) {
        // If there's a gap
        if (all_intervals[i].start > last_end) {
            result.push_back({last_end, all_intervals[i].start});
        }
        // Update the last seen end time
        last_end = std::max(last_end, all_intervals[i].end);
    }
    return result;
}
// class Interval {
// public:
//     int start;
//     int end;
//     ...
// };