Lean4

35. Merge intervals

MediumProgramAcademy Pass20 points

Each pair (a, b) with a ≤ b is the closed interval from a to b. Write merge intervals, which merges every group of overlapping intervals and returns the result sorted by start.

Intervals that only touch, such as (1, 4) and (4, 5), overlap and merge into (1, 5). The input may be in any order.

Examples

  1. Inputmerge [(1, 3), (2, 6), (8, 10), (15, 18)]Output[(1, 6), (8, 10), (15, 18)]
  2. Inputmerge [(1, 4), (4, 5)]Output[(1, 5)]
  3. Inputmerge [(8, 10), (1, 3)]Output[(1, 3), (8, 10)]

Submitting also runs 8 hidden tests.

Constraints

  • Hidden tests include 20,000 intervals, so sorting must take O(n log n).
sortinglistsperformance

Running and submitting solutions, the hints and the editorial come with the Academy Pass. The daily problem is open to every account.

Learn the ideas

Similar problems

Solution.lean
Loading…
Loading editor…
3#guard (merge [(1, 3), (2, 6), (8, 10), (15, 18)]) = ([(1, 6), (8, 10), (15, 18)])
4#guard (merge [(1, 4), (4, 5)]) = ([(1, 5)])
5#guard (merge [(8, 10), (1, 3)]) = ([(1, 3), (8, 10)])
examples

Run checks your code against the examples and your custom inputs and records nothing. Submit also runs the hidden tests, confirms the axioms your proof uses and records the result. Each uses one compiler check.

ReadyLn 1, Col 1Lean 4
Draft saved in this browser