Skip to content
Hello Python

Coalesce Busy Blocks

Practice ExerciseIntermediateMediumMerge IntervalsArrayInterval

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 coalesce_busy_blocks(blocks). Each block is a half-open [start, end) pair. Merge blocks only when they overlap; touching blocks such as [1, 3) and [3, 5) remain separate. Return new sorted lists and do not mutate blocks.

Starter code

def coalesce_busy_blocks(blocks):
    pass
Test cases

overlap-not-touch

{
  "args": [
    [
      [
        5,
        8
      ],
      [
        1,
        4
      ],
      [
        3,
        6
      ],
      [
        8,
        10
      ]
    ]
  ]
}

Expected: [[1,8],[8,10]]

nested-blocks

{
  "args": [
    [
      [
        1,
        9
      ],
      [
        2,
        3
      ],
      [
        4,
        8
      ]
    ]
  ]
}

Expected: [[1,9]]

Wizard outline
  1. Step 1: Sort independent blocks

    Create a deterministic copy without mutating the caller. Sorted starts make a single frontier sufficient for every later decision.

  2. Step 2: Extend an overlap frontier

    Merge overlapping blocks before refining boundary equality. After sorting, only the most recent merged frontier can interact with the next block.

  3. Step 3: Preserve touching blocks

    Complete the half-open contract at equal boundaries. A block ending at t excludes t, while a block starting at t includes it, so they share no time.

Footguns and prerequisites
  • Using <= merges touching half-open blocks that do not overlap.
  • Replacing the merged end without max can shrink nested coverage.
  • arrays strings two pointers sliding window
Reviewed references
Recommended approach and implementation

Sort copied half-open blocks and extend only the last merged block when strict overlap exists.

Why it works: Sorted order makes the last merged block the only possible overlap. Strict comparison merges exactly shared time and preserves touching but disjoint half-open boundaries.

def coalesce_busy_blocks(blocks):
    merged = []
    for start, end in sorted([list(block) for block in blocks]):
        if merged and start < merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged