Interval Manipulation Techniques

Hello! In our last lesson, we took a deep dive into hash maps and saw how they offer an elegant way to optimize lookup-heavy problems, a common requirement in backend services. We explored patterns like frequency counting and complement lookup, which are essential for your interview toolkit.

Today, we're shifting gears to another crucial pattern in algorithm design: intervals. Problems involving intervals are frequently used in interviews to test your ability to handle ranges of data, a scenario that maps directly to real-world backend challenges like managing schedules, allocating resources, or processing time-series data. This lesson will equip you with the fundamental techniques to solve problems involving merging and inserting intervals, building a solid foundation for more complex variations you might encounter.

What is an Interval?

At its core, an interval is simply a pair of numbers representing a start and an end point, usually written as [start, end]. The core of any interval problem lies in understanding how two intervals relate to each other. Do they overlap? Is one completely contained within another? Or are they entirely separate?

The following image illustrates the six fundamental ways two intervals, 'a' and 'b', can interact. Understanding these relationships is the first step toward building a systematic approach to solving interval problems.

A key insight is that two intervals, a = [a_start, a_end] and b = [b_start, b_end], overlap if and only if a_start <= b_end and b_start <= a_end. This simple logical test is the cornerstone of the merge algorithm we will explore next.

The Merge Intervals Pattern

The most common interval problem asks you to take a collection of potentially overlapping intervals and merge them into a set of mutually exclusive (non-overlapping) intervals. For example, given [[1, 4], [2, 5], [7, 9]], the intervals [1, 4] and [2, 5] overlap and should be merged into [1, 5], resulting in the final output [[1, 5], [7, 9]].

A naive approach would be to compare every interval with every other interval, which would be an inefficient $O(n^2)$ solution. The key to an optimal solution is a powerful two-step strategy: Sort, then Scan.

If we sort the intervals based on their start times, the problem becomes much simpler. Once sorted, we only need to compare each interval with the most recently processed one to check for an overlap. This eliminates the need to look ahead or back, allowing for a single linear pass.

The following video provides an excellent visualization of this process on a number line and walks through the implementation. Pay close attention to how sorting enables the simple, linear-time merge logic.

Now that you have the visual intuition, let's solidify the theory. The following reading provides a structured breakdown of the algorithm, including the formal steps and complexity analysis.

To summarize the optimized algorithm for merging intervals:

1. Sort the collection of intervals by their start times. This costs $O(n\log n)$.
2. Initialize an empty merged list and add the first sorted interval to it.
3. Iterate through the remaining sorted intervals from the second one onward.
4. For each current interval, get a reference to the last interval in the merged list.
5. Check for overlap: if current.start <= last.end:
   • If they overlap, merge them by updating the last interval's end: last.end = max(last.end, current.end).
6. Else (no overlap):
   • Add the current interval to the merged list.
7. The process takes a single pass, which is $O(n)$. The total time complexity is dominated by the sort, making it $O(n\log n)$. The space complexity is $O(n)$ to store the result (or $O(1)$ if we can modify the input array and if the sorting algorithm used is in-place, not counting the output).

Here is what a clean implementation looks like in Go, your primary language:

package main

import (
	"fmt"
	"sort"
)

// max returns the larger of two integers.
func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func merge(intervals [][]int) [][]int {
	if len(intervals) <= 1 {
		return intervals
	}

	// 1. Sort intervals based on their start time.
	// In Go, we use sort.Slice with a custom less function.
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	// 2. Initialize merged list with the first interval.
	merged := [][]int{intervals[0]}

	// 3. Iterate through the rest of the intervals.
	for i := 1; i < len(intervals); i++ {
		current := intervals[i]
		// Get a pointer to the last interval in the merged slice.
		// Note: Using a pointer/index is more efficient than repeatedly copying.
		last := &merged[len(merged)-1]

		// 4. Check for overlap.
		if current[0] <= (*last)[1] {
			// 5. Merge by updating the end of the last interval.
			(*last)[1] = max((*last)[1], current[1])
		} else {
			// 6. No overlap, append the current interval.
			merged = append(merged, current)
		}
	}

	return merged
}

func main() {
	intervals1 := [][]int{{1, 3}, {2, 6}, {8, 10}, {15, 18}}
	fmt.Println(merge(intervals1)) // Output: [[1 6] [8 10] [15 18]]

	intervals2 := [][]int{{1, 4}, {4, 5}}
	fmt.Println(merge(intervals2)) // Output: [[1 5]]
}

The Insert Interval Pattern

A common variation is the "Insert Interval" problem. Here, you are given a list of non-overlapping intervals that are already sorted by their start times, and you need to insert a new interval, merging if necessary.

Because the initial list is sorted, we don't need to perform the $O(n\log n)$ sorting step. This allows for a more efficient $O(n)$ solution where we can find the correct position for the new interval and perform the merge in a single pass.

The logic can be broken down into three clean phases:

1. Add all intervals from the original list that come before the new interval (i.e., their end is less than the new interval's start) to the result.
2. Merge the new interval with all subsequent intervals from the original list that overlap with it. This is done by iteratively updating the start and end of our new interval.
3. Add the (now possibly expanded) new interval to the result.
4. Add all remaining intervals from the original list that come after the new interval to the result.

The following resource provides a clear walkthrough of this algorithm.

Here is a Go implementation that follows this clean, three-part logic:

package main

import "fmt"

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func insert(intervals [][]int, newInterval []int) [][]int {
	var result [][]int
	i := 0

	// Phase 1: Add all intervals that end before the new interval starts.
	for i < len(intervals) && intervals[i][1] < newInterval[0] {
		result = append(result, intervals[i])
		i++
	}

	// Phase 2: Merge the new interval with all overlapping intervals.
	// The loop continues as long as there is an overlap.
	for i < len(intervals) && intervals[i][0] <= newInterval[1] {
		newInterval[0] = min(newInterval[0], intervals[i][0])
		newInterval[1] = max(newInterval[1], intervals[i][1])
		i++
	}
	// After the loop, newInterval is fully merged.
	result = append(result, newInterval)

	// Phase 3: Add all remaining intervals.
	for i < len(intervals) {
		result = append(result, intervals[i])
		i++
	}

	return result
}

func main() {
	intervals := [][]int{{1, 2}, {3, 5}, {6, 7}, {8, 10}, {12, 16}}
	newInterval := []int{4, 8}
	fmt.Println(insert(intervals, newInterval)) // Output: [[1 2] [3 10] [12 16]]
}

Conclusion

In this lesson, we've dissected the "Merge Intervals" pattern, a fundamental technique for a broad class of problems. You've learned not just the "what" but the "why" behind the solutions, which is critical for adapting these patterns to new problems in an interview setting.

Key Takeaways:

• Sorting is Key: For most interval problems, sorting the intervals by their start time is the crucial first step that simplifies the logic and enables an efficient linear scan.
• Merge Logic: When merging two overlapping intervals [s1, e1] and [s2, e2], the new merged interval is [min(s1, s2), max(e1, e2)]. Since we sort by start time, this simplifies to [s1, max(e1, e2)].
• Insert Logic: The "Insert Interval" problem is an optimization where you can leverage the pre-sorted input to find the merge point in $O(n)$ time, avoiding a full re-sort.
• Problem-Solving Pattern: The general approach is to identify non-overlapping parts and merging parts. This can often be implemented as a clean, multi-phase process.

In our next lesson, we'll explore the prefix sum technique. This pattern is another powerful tool for efficiently handling range-based queries on arrays, providing a different perspective on solving problems involving contiguous blocks of data.