Algorithm for Merging Overlapping Intervals: Greedy Implementation Guide

Merge overlapping intervals by first sorting them by start time, then iterating through the sorted list to combine any interval that overlaps with the previous one, resulting in O(N log N) time complexity.

The algorithm for merging overlapping intervals is a fundamental greedy algorithm commonly asked in technical interviews. This guide examines the implementation found in the kdn251/interviews repository, which provides a clean, efficient solution used across multiple company-specific interview preparations including Google, LinkedIn, and Twitter.

How the Greedy Algorithm Works

The greedy approach to merging intervals relies on two key insights: overlapping intervals must be adjacent after sorting, and a single linear scan can resolve all overlaps once the intervals are ordered.

Step 1: Sort Intervals by Start Time

First, sort the collection of intervals by their starting values. When two intervals share the same start value, sort by their end values to ensure deterministic ordering.

In kdn251/interviews, this is implemented in leetcode/array/MergeIntervals.java using Arrays.sort with a custom comparator:

// Lines 23-30 in MergeIntervals.java
Arrays.sort(intervals, new Comparator<Interval>() {
    @Override
    public int compare(Interval i1, Interval i2) {
        if (i1.start == i2.start) {
            return i1.end - i2.end;
        }
        return i1.start - i2.start;
    }
});

Step 2: Linear Scan and Merge

Initialize a result list and iterate through the sorted intervals:

• If the result list is empty, add the current interval.
• If the current interval's start is greater than the end of the last interval in the result, they do not overlap—add the current interval as a new entry.
• Otherwise, the intervals overlap. Update the end of the last result interval to be the maximum of its current end and the current interval's end.

This logic appears in the merge method of the repository's implementation.

Complete Implementation Example

Here is a runnable example based on the kdn251/interviews source code:

import java.util.*;

public class MergeIntervals {
    static class Interval {
        int start, end;
        Interval(int s, int e) { start = s; end = e; }
        @Override public String toString() { return "[" + start + "," + end + "]"; }
    }

    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 1) {
            return intervals;
        }
        
        // Sort by start time, then end time
        Collections.sort(intervals, (i1, i2) -> {
            if (i1.start == i2.start) return i1.end - i2.end;
            return i1.start - i2.start;
        });
        
        List<Interval> result = new ArrayList<>();
        for (Interval interval : intervals) {
            if (result.isEmpty() || result.get(result.size() - 1).end < interval.start) {
                result.add(interval);
            } else {
                result.get(result.size() - 1).end = Math.max(result.get(result.size() - 1).end, interval.end);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        MergeIntervals solution = new MergeIntervals();
        List<Interval> intervals = Arrays.asList(
            new Interval(1, 3),
            new Interval(2, 6),
            new Interval(8, 10),
            new Interval(15, 18)
        );
        
        List<Interval> merged = solution.merge(intervals);
        System.out.println("Merged intervals: " + merged);
        // Output: Merged intervals: [[1,6], [8,10], [15,18]]
    }
}

Complexity Analysis

The algorithm for merging overlapping intervals achieves optimal efficiency through its greedy design.

Time Complexity: O(N log N), where N is the number of intervals. The sorting step dominates the runtime, while the linear scan operates in O(N).

Space Complexity: O(N) for the output list that stores the merged intervals. The sorting may require O(log N) to O(N) auxiliary space depending on the Java implementation, but the additional space used by the algorithm itself is minimal.

Repository Structure and Variations

The kdn251/interviews repository implements this algorithm across multiple locations for interview preparation:

• leetcode/array/MergeIntervals.java — The primary implementation with detailed comparator logic
• company/google/MergeIntervals.java — Adapted for Google interview scenarios
• company/linkedin/MergeIntervals.java — LinkedIn-specific preparation version
• company/twitter/MergeIntervals.java — Twitter interview practice implementation

All versions maintain the same core greedy algorithm but may include variations in input handling or class structure specific to their target company's interview patterns.

Summary

• The algorithm for merging overlapping intervals uses a greedy approach that sorts intervals by start time, then merges them in a single linear pass.
• Time complexity is O(N log N) due to the sorting step, with O(N) space required for the output.
• The implementation in kdn251/interviews uses Arrays.sort with a custom comparator to handle the sorting logic, followed by a straightforward iteration to detect overlaps.
• This solution appears consistently across multiple company-specific interview preparation files in the repository, demonstrating its importance as a fundamental algorithmic pattern.

Frequently Asked Questions

What makes the interval merging algorithm "greedy"?

The algorithm is considered greedy because it makes the locally optimal choice at each step—merging the current interval with the previous one if they overlap—without backtracking. By sorting the intervals first, the greedy choice of immediate merging whenever possible leads to the globally optimal solution of minimal non-overlapping intervals.

Can the algorithm handle intervals with negative numbers or unsorted input?

Yes, the algorithm handles negative start and end values naturally because the sorting comparator orders them correctly regardless of sign. The implementation explicitly expects unsorted input and performs the O(N log N) sort as its first step, making it robust for any valid interval collection.

How does the space complexity change if we modify the array in-place instead of creating a new list?

If modifying the input array in-place, the space complexity can be reduced to O(1) auxiliary space (excluding the output). However, the kdn251/interviews implementation uses O(N) space for the result list because it preserves the input and builds a new collection of merged intervals, which is generally safer for functional programming patterns and interview expectations.

What is the difference between the LeetCode version and the company-specific versions in the repository?

The core algorithm remains identical across all versions in kdn251/interviews. The differences lie primarily in packaging, class naming conventions, and sometimes the specific Interval class definition structure. The company-specific versions (Google, LinkedIn, Twitter) are organized to help candidates practice in contexts resembling those companies' interview environments, but they all implement the same O(N log N) sorting and linear merging strategy.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}