🦄 Merge the Moons: Merge Intervals

Difficulty: Intermediate Tags: sorting, intervals, greedy-algorithm Series: CS 102: Problem Solving & Logic

Problem

In the mystical realm, moon phases are represented as time intervals. When moon phases overlap, they merge into a single continuous phase. Your task is to merge all overlapping intervals.

Given a collection of intervals where each interval is [start, end], merge all overlapping intervals and return a list of non-overlapping intervals sorted by start time.

Two intervals overlap if they share any common point. For example, [1,3] and [2,6] overlap because they both include the range [2,3].

Real-World Application

Interval merging appears in: - Calendar applications - finding free time slots, merging meeting schedules - Log analysis - consolidating time ranges for events, finding uptime periods - Resource allocation - managing booking systems, conference room scheduling - Compiler optimization - register allocation, live variable analysis - Network monitoring - detecting connection periods, downtime windows - Database query optimization - index range merging

Input

data = list[list[int]]  # List of intervals [start, end]

Output

list[list[int]]  # Merged non-overlapping intervals, sorted by start

Constraints

• Number of intervals ≤ 100,000
• Each interval satisfies: start ≤ end
• Interval values are integers

Examples

Example 1: Basic Overlapping Intervals

Input: [[1,3], [2,6], [8,10], [15,18]]

Output: [[1,6], [8,10], [15,18]]

Explanation: - [1,3] and [2,6] overlap → merge to [1,6] - [8,10] doesn't overlap with anything - [15,18] doesn't overlap with anything - Result: 3 non-overlapping intervals

Example 2: Adjacent Intervals

Input: [[1,4], [4,5]]

Output: [[1,5]]

Explanation: - [1,4] and [4,5] touch at point 4 → they overlap - Merge to [1,5]

Example 3: No Overlapping

Input: [[1,2], [3,4], [5,6]]

Output: [[1,2], [3,4], [5,6]]

Explanation: - No intervals overlap - Return as-is (already sorted)

Example 4: Complete Overlap

Input: [[1,10], [2,3], [4,5], [6,7]]

Output: [[1,10]]

Explanation: - [2,3], [4,5], and [6,7] are all completely contained within [1,10] - All merge into single interval [1,10]

Example 5: Unsorted Input

Input: [[6,8], [1,3], [2,4], [9,10]]

Output: [[1,4], [6,8], [9,10]]

Explanation: - First sort by start: [[1,3], [2,4], [6,8], [9,10]] - [1,3] and [2,4] overlap → merge to [1,4] - [6,8] and [9,10] don't overlap - Result: [[1,4], [6,8], [9,10]]

What You'll Learn

• How to use sorting to simplify interval problems
• The greedy sweep-line algorithm technique
• When intervals are considered overlapping
• How to efficiently merge data ranges

Why This Matters

Interval merging is one of the most common interview questions. It tests your ability to: - Recognize when sorting simplifies a problem - Implement a greedy algorithm with proper edge case handling - Work with ranges and overlapping conditions

Starter Code

def challenge_function(data):
    """
    Merge all overlapping intervals.

    Args:
        data: list of intervals [start, end]

    Returns:
        list of merged non-overlapping intervals, sorted by start
    """
    # Your implementation here
    pass