Skip to content
Hello Python

Select the Most Non-Overlapping Intervals

Practice ExerciseIntermediateMediumMerge IntervalsIntervalGreedy

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 maximum_non_overlapping(intervals). Intervals are [start, end] with start < end and touching endpoints are compatible. Return the maximum count of pairwise non-overlapping intervals.

Starter code

def maximum_non_overlapping(intervals):
    pass
Test cases

greedy-choice

{
  "args": [
    [
      [
        1,
        4
      ],
      [
        2,
        3
      ],
      [
        3,
        5
      ],
      [
        5,
        7
      ]
    ]
  ]
}

Expected: 3

touching

{
  "args": [
    [
      [
        0,
        1
      ],
      [
        1,
        2
      ],
      [
        2,
        3
      ]
    ]
  ]
}

Expected: 3

Wizard outline
  1. Step 1: Define the empty schedule

    Return zero when no interval exists. The greedy loop begins from a valid empty selection.

  2. Step 2: Choose the exchange-safe first interval

    Select one interval with the earliest end. Replacing any first selected interval with an earlier-finishing one cannot reduce the remaining room.

  3. Step 3: Extend the schedule greedily

    Accept every next interval compatible with the last choice. Earliest-finish order makes each accepted choice exchange-safe and leaves maximal room for the suffix.

Footguns and prerequisites
  • Sorting by start can block several short intervals.
  • Using start > end incorrectly rejects touching intervals.
  • functions
  • lists and tuples
  • control flow
Reviewed references
Recommended approach and implementation

Sort by finish time and accept each interval whose start is at least the previous accepted end.

Why it works: An optimal schedule can replace its first interval with the earliest-finishing interval without losing compatibility. Repeating this exchange argument on the remaining suffix proves the greedy count optimal.

def maximum_non_overlapping(intervals):
    count = 0
    last_end = None
    for start, end in sorted(intervals, key=lambda interval: (interval[1], interval[0])):
        if last_end is None or start >= last_end:
            count += 1
            last_end = end
    return count