{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Merge Intervals – Solution & Complexity

Interview solutions
/
Merge Intervals
Quick practice for Merge Intervals: 3 reasoning beats, no typing

Watch: Merge Intervals by sorting

Sort the intervals by start time. Then walk them in order: if the next one starts before the last merged one ends, extend the end; otherwise start a new interval. O(n log n) for the sort, one pass after.

Solution Walkthrough

  1. Step 1: Understanding the Problem

    • Given an array of intervals where each interval is represented as [start, end], merge overlapping intervals.
    • The goal is to return a list of non-overlapping intervals that cover all intervals in the input array.

  2. Step 2: Sort Intervals by Start Time

    • Sort the intervals based on their starting values.
    • This will make it easier to detect overlaps by ensuring that any overlapping intervals are adjacent.
    def merge_intervals(intervals: list) -> list:
    intervals.sort(key=lambda x: x[0])
    return intervals

  3. Step 3: Initialize Merged Intervals List

    • Create an empty list merged to store the merged intervals.
    • The list will eventually contain only the non-overlapping intervals.
    def merge_intervals(intervals: list) -> list:
    intervals.sort(key=lambda x: x[0])
    merged = []  # List to store merged intervals
    return merged

  4. Step 4: Iterate Through Sorted Intervals

    • For each interval, check if it overlaps with the last interval in the merged list.
    • If it does overlap, merge the intervals by extending the end of the last interval in merged.
    • If it doesn’t overlap, simply add it to merged.
    def merge_intervals(intervals: list) -> list:
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        # If merged is empty or there is no overlap, add interval
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            # Merge the current interval with the last one in merged
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

  5. Step 5: Return Merged Intervals

    • After processing all intervals, return the merged list which contains only non-overlapping intervals.
    def merge_intervals(intervals: list) -> list:
    intervals.sort(key=lambda x: x[0])
    merged = []
    for interval in intervals:
        if not merged or merged[-1][1] < interval[0]:
            merged.append(interval)
        else:
            merged[-1][1] = max(merged[-1][1], interval[1])
    return merged

  6. Step 6: Consider Edge Cases

    • Edge cases include:
      • Only one interval, which should be returned as-is.
      • Non-overlapping intervals, where each interval is added to merged without modification.
      • Intervals that completely overlap each other.

FAQ

See also

Practice Merge Intervals online (run code in the browser)Non-overlapping Intervals solution (medium)3Sum solution (medium)3Sum Closest solution (medium)Combination Sum II solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?