Data Structure1 Practice55 Interview

Interval

GuideCode Labs

Start-end pair representing a range for overlap, scheduling, and sweep-line problems. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Interval when the prompt's constraints and required operations match this shape: Start-end pair representing a range for overlap, scheduling, and sweep-line problems.

On this page · Mental Model

Checking your account…

Mental Model

An interval is a start/end pair plus a boundary convention. Overlap cannot be decided until the contract says whether endpoints are closed, open, or half-open.

Endpoint Semantics Come First

Closed [start, end] intervals include both endpoints, so [1, 3] and [3, 5] touch and overlap at 3. Half-open [start, end) intervals make adjacent ranges non-overlapping. Write the comparison from that rule instead of memorizing < versus <=.

Normalize Overlapping Closed Intervals

Sort by start, then keep one merged frontier. If the next start is no greater than the frontier end, extend the end; otherwise the frontier is final. Sorting dominates at O(n log n), and copying output avoids mutating caller-owned interval lists.

Merge Closed Intervals

Reference

def normalize_closed_intervals(intervals):
    merged = []
    for start, end in sorted((start, end) for start, end in intervals):
        if not merged or start > merged[-1][1]:
            merged.append([start, end])
        else:
            merged[-1][1] = max(merged[-1][1], end)
    return merged

Practice

Implement normalize_closed_intervals(intervals). Sort copies and merge overlap or touching boundaries without mutating input.

def normalize_closed_intervals(intervals):
    return sorted([list(interval) for interval in intervals])

Public tests

Verify closed-boundary merging

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Insert into an Ordered Disjoint Set

When existing intervals are already sorted and disjoint, copy intervals strictly before the new range, merge every touching range, then append the untouched suffix. This is O(n) without re-sorting.

Insert into Disjoint Intervals

Reference

def insert_closed(intervals, new_interval):
    result = []
    index = 0
    start, end = new_interval
    while index < len(intervals) and intervals[index][1] < start:
        result.append(intervals[index].copy())
        index += 1
    while index < len(intervals) and intervals[index][0] <= end:
        start = min(start, intervals[index][0])
        end = max(end, intervals[index][1])
        index += 1
    result.append([start, end])
    result.extend(interval.copy() for interval in intervals[index:])
    return result

Practice

Implement insert_closed(intervals, new_interval). Existing closed intervals are sorted and disjoint; return the merged insertion in O(n).

def insert_closed(intervals, new_interval):
    return intervals + [new_interval]

Public tests

Verify linear merged insertion

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose Intervals or Events

Use interval merging when ranges themselves are the output. Use start/end events for maximum overlap, room counts, or time-varying state; event tie order must reflect closed versus half-open semantics. Use a difference array when the coordinate domain is small and dense.

Common Pitfalls

Applying the wrong touching rule silently changes scheduling results.
Sorting by end for a merge frontier does not guarantee all overlaps become adjacent.
Mutating input pairs can violate ownership expectations.
Re-sorting an already ordered insertion problem loses the intended linear bound.

Explain It in an Interview

State endpoint semantics first, then define what the merged frontier covers. Explain why sorted start order proves no finalized interval can overlap a later one.

Normalize Closed Intervals(opens in a new tab) practices the frontier; Merge Intervals(opens in a new tab) requires recognizing that normalization pattern.

Python Version Note

Python 3.11+

The examples use standard Python containers and syntax available in the supported browser runtime; Interval itself is taught as an interview abstraction.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Core Interval workflow	`O(n log n)`	`O(n log n)`	Sort copied intervals by start and maintain one merged frontier, extending it whenever the next closed interval starts at or before the frontier end.

Space

O(n) for the demonstrated Interval workflow.

Assumptions

State the concrete operation and representation before claiming a bound; tree height and graph density can change it.
The bound counts the operations in Normalize Closed Intervals and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

State the precise Interval invariant before coding and preserve it after every update, traversal step, or recursive return.
Sort intervals by start before making local merge decisions. This remains true after every accepted operation.
Maintain one merged frontier whose end is the maximum covered endpoint. This remains true after every accepted operation.

When To Use Or Avoid Interval

Use It When

Use Interval when its representation directly supports the prompt's repeated query or update.
Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Leaving the core transition unfinished

Placeholder code cannot preserve the Interval invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

def normalize_closed_intervals(intervals):
    pass

Use instead

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

Where you will hit this: Normalize Closed Intervals(opens in a new tab)

Breaking the central invariant

Uses a strict comparison and therefore fails to merge intervals that share a closed endpoint.

Prevent it: Keep this invariant visible while editing: State the precise Interval invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

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

Use instead

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

Where you will hit this: Normalize Closed Intervals(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O(n log n).

Avoid

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

Use instead

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

Where you will hit this: Merge Intervals(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27

Checking your account…

Interval Code Labs

Mental Model

Endpoint Semantics Come First

Normalize Overlapping Closed Intervals

Public tests

Insert into an Ordered Disjoint Set

Public tests

Choose Intervals or Events

Common Pitfalls

Explain It in an Interview

Python Version Note

Complexity & Invariants

Space

Assumptions

Invariants Worth Saying Aloud

When To Use Or Avoid Interval

Use It When

Choose Another Tool When

Common Pitfalls

Leaving the core transition unfinished

Breaking the central invariant

Hiding Python work inside the loop

Related Practice

Related Interview Problems

Reviewed References