Skip to content
Hello Python

Normalize Closed Intervals

Practice ExerciseIntermediateMediumArrayInterval

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement normalize_closed_intervals(intervals). Each interval is a closed [start, end] pair with start <= end. Return new sorted lists that merge every overlap and every touching boundary. Do not mutate the input.

Starter code

def normalize_closed_intervals(intervals):
    pass
Test cases

overlap-and-disjoint

{
  "args": [
    [
      [
        5,
        7
      ],
      [
        1,
        3
      ],
      [
        2,
        6
      ],
      [
        10,
        12
      ]
    ]
  ]
}

Expected: [[1,7],[10,12]]

touching-closed

{
  "args": [
    [
      [
        1,
        2
      ],
      [
        2,
        4
      ],
      [
        6,
        6
      ]
    ]
  ]
}

Expected: [[1,4],[6,6]]

Wizard outline
  1. Step 1: Copy and sort intervals

    Create new mutable interval lists ordered by start and then end. A copied sorted order enables one forward merge without mutating input.

  2. Step 2: Extend the overlap frontier

    Merge an overlapping interval by increasing only the last output end. Sorted starts guarantee that an overlap can affect only the latest merged interval.

  3. Step 3: Merge touching closed boundaries

    Treat equality at the frontier as overlap because both intervals include the boundary. Closed interval semantics require [1,2] and [2,4] to share the value two.

Footguns and prerequisites
  • Using a strict overlap check leaves touching closed intervals separate.
  • Sorting the caller list in place violates the no-mutation contract.
  • arrays strings two pointers sliding window
Reviewed references
Recommended approach and implementation

Sort copied intervals by start and maintain one merged frontier, extending it whenever the next closed interval starts at or before the frontier end.

Why it works: Sorted order guarantees no interval before the frontier can interact with a later interval except through the frontier. Each overlap or touch extends that exact connected component, while a larger start begins a disjoint component.

def normalize_closed_intervals(intervals):
    ordered = sorted([list(interval) for interval in intervals])
    merged = []
    for start, end in ordered:
        if merged and start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged