import Mathlib /-! # Merge Intervals Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input. ## Constraints - 1 <= intervals.length <= 10^4 - intervals[i].length == 2 - 0 <= starti <= endi <= 10^4 ## Provided examples - `intervals = [[1, 4], [4, 5]]` → `[[1, 5]]` - `intervals = [[1, 4], [2, 3]]` → `[[1, 4]]` - `intervals = [[1, 10], [2, 6], [9, 12]]` → `[[1, 12]]` ## Synthesized negative examples - invalid input: `intervals = []` ([structural] a predicate that admits 1 <= intervals.length <= 10^4. empty where at least one interval is required) - invalid input: `intervals = [[1]]` ([structural] a predicate that admits intervals[i].length == 2. one-element interval; a predicate checking only outer length accepts it) - invalid input: `intervals = [[-1, 3]]` ([structural] a predicate that admits 0 <= starti <= endi <= 10^4. start one below zero; a predicate checking only end accepts it) - `intervals = [[1, 4], [4, 5]]` → `[[1, 4], [4, 5]]` is wrong ([structural] specification omits the overlap check; accepts unmerged overlapping intervals. overlaps at 4, but covers all input) - `intervals = [[1, 4], [2, 3]]` → `[[0, 4]]` is wrong ([structural] left endpoint computed as start-1. interval starts one early; all inputs still covered) - `intervals = [[1, 10], [2, 6], [9, 12]]` → `[[1, 11]]` is wrong ([structural] merged interval endpoint is one below the true value. covers all but the last input interval) -/ namespace PMergeIntervals abbrev Input := List (List Int) abbrev Output := List (List Nat) /-! ### Specification helpers -/ /-- Start endpoint of a list-encoded output interval, 0 when absent. -/ def ivStart (iv : List Nat) : Nat := iv.getD 0 0 /-- End endpoint of a list-encoded output interval, 0 when absent. -/ def ivEnd (iv : List Nat) : Nat := iv.getD 1 0 /-- Start endpoint of a list-encoded input interval, 0 when absent. -/ def ivStartI (iv : List Int) : Int := iv.getD 0 0 /-- End endpoint of a list-encoded input interval, 0 when absent. -/ def ivEndI (iv : List Int) : Int := iv.getD 1 0 /-- Closed intervals `a` and `b` overlap or touch. -/ def Overlaps (a b : List Nat) : Prop := ivStart a ≤ ivEnd b ∧ ivStart b ≤ ivEnd a /-- Output interval `o` contains input interval `i`, endpoints compared in `Int`. -/ def Covers (o : List Nat) (i : List Int) : Prop := (ivStart o : Int) ≤ ivStartI i ∧ ivEndI i ≤ (ivEnd o : Int) /-- Every real point of output interval `o` lies in some input interval. -/ def LiesInUnion (o : List Nat) (input : List (List Int)) : Prop := ∀ x : ℝ, x ∈ Set.Icc (ivStart o : ℝ) (ivEnd o : ℝ) → ∃ i ∈ input, x ∈ Set.Icc (ivStartI i : ℝ) (ivEndI i : ℝ) /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 10^4 intervals, each `[s, e]` with `0 ≤ s ≤ e ≤ 10^4`. -/ def isValidInput (input : Input) : Bool := decide (1 ≤ input.length) && decide (input.length ≤ 10^4) && input.all fun iv => match iv with | [s, e] => decide (0 ≤ s) && decide (s ≤ e) && decide (e ≤ 10^4) | _ => false /-! ### Ideal specification (P_spec) -/ /-- `result` merges `input`: well-formed, start-sorted, pairwise disjoint intervals covering every input interval, each lying in the union of the input intervals. -/ def mergeIntervals_spec (input : Input) (result : Output) : Prop := (∀ o ∈ result, o.length = 2 ∧ ivStart o ≤ ivEnd o) ∧ List.Pairwise (fun a b => ivStart a ≤ ivStart b) result ∧ List.Pairwise (fun a b => ¬ Overlaps a b) result ∧ (∀ i ∈ input, ∃ o ∈ result, Covers o i) ∧ (∀ o ∈ result, LiesInUnion o input) /-! ### Decidable specification (P_check) -/ /-- Doubled point `x2` (the half-integer `x2/2`) lies in input interval `i`. -/ def halfPointIn (x2 : Int) (i : List Int) : Bool := decide (2 * ivStartI i ≤ x2 ∧ x2 ≤ 2 * ivEndI i) /-- Every half-integer point of output interval `o` lies in some input interval. -/ def liesInUnionCheck (o : List Nat) (input : List (List Int)) : Bool := (List.range (2 * (ivEnd o - ivStart o) + 1)).all fun k => input.any (halfPointIn (2 * (ivStart o : Int) + (k : Int))) /-- Boolean overlap test matching `Overlaps`. -/ def overlapsCheck (a b : List Nat) : Bool := ivStart a ≤ ivEnd b && ivStart b ≤ ivEnd a /-- Boolean containment test matching `Covers`. -/ def coversCheck (o : List Nat) (i : List Int) : Bool := (ivStart o : Int) ≤ ivStartI i && ivEndI i ≤ (ivEnd o : Int) /-- Boolean pairwise test: `r` holds for every ordered pair of distinct entries. -/ def pairwiseCheck {α : Type} (r : α → α → Bool) : List α → Bool | [] => true | x :: xs => xs.all (r x) && pairwiseCheck r xs /-- Executable checker for `mergeIntervals_spec`, real-point coverage checked at half-integer points. -/ def mergeIntervals_check (input : Input) (result : Output) : Bool := decide (∀ o ∈ result, o.length = 2 ∧ ivStart o ≤ ivEnd o) && decide (List.Pairwise (fun a b => ivStart a ≤ ivStart b) result) && pairwiseCheck (fun a b => !overlapsCheck a b) result && input.all (fun i => result.any fun o => coversCheck o i) && result.all fun o => liesInUnionCheck o input theorem pairwiseCheck_iff {α : Type} (r : α → α → Bool) (xs : List α) : pairwiseCheck r xs = true ↔ List.Pairwise (fun a b => r a b = true) xs := by induction xs with | nil => simp [pairwiseCheck] | cons x xs ih => simp [pairwiseCheck, ih, List.pairwise_cons] theorem root_of_bridges (bridge : ∀ (o : List Nat) (input : Input), ivStart o ≤ ivEnd o → (liesInUnionCheck o input = true ↔ LiesInUnion o input)) (input : Input) (result : Output) : mergeIntervals_check input result ↔ mergeIntervals_spec input result := by simp only [mergeIntervals_check, mergeIntervals_spec, Bool.and_eq_true, decide_eq_true_eq, pairwiseCheck_iff, Bool.not_eq_true', overlapsCheck, Bool.and_eq_true, Bool.and_eq_false_eq_eq_false_or_eq_false, decide_eq_false_iff_not, List.all_eq_true, List.any_eq_true, coversCheck, decide_eq_true_eq] simp only [Overlaps, Covers, not_and_or] constructor · rintro ⟨⟨⟨⟨hw, hs⟩, hd⟩, hc⟩, hu⟩ exact ⟨hw, hs, hd, hc, fun o ho => (bridge o input (hw o ho).2).mp (hu o ho)⟩ · rintro ⟨hw, hs, hd, hc, hu⟩ exact ⟨⟨⟨⟨hw, hs⟩, hd⟩, hc⟩, fun o ho => (bridge o input (hw o ho).2).mpr (hu o ho)⟩ theorem union_bridge (o : List Nat) (input : Input) (hab : ivStart o ≤ ivEnd o) : liesInUnionCheck o input = true ↔ LiesInUnion o input := by simp only [liesInUnionCheck, List.all_eq_true, List.mem_range, List.any_eq_true, halfPointIn, decide_eq_true_eq] constructor · intro hc x hx have sample : ∀ z : Int, 2 * (ivStart o : Int) ≤ z → z ≤ 2 * (ivEnd o : Int) → ∃ i ∈ input, 2 * ivStartI i ≤ z ∧ z ≤ 2 * ivEndI i := by intro z hzlo hzhi let k := (z - 2 * (ivStart o : Int)).toNat have hkcast : (k : Int) = z - 2 * (ivStart o : Int) := Int.toNat_of_nonneg (by omega) have hk : k < 2 * (ivEnd o - ivStart o) + 1 := by omega have heq : 2 * (ivStart o : Int) + (k : Int) = z := by omega simpa only [heq] using hc k hk have hxlo := hx.1 have hxhi := hx.2 let n : Int := ⌊x⌋ have hnlo : (n : ℝ) ≤ x := Int.floor_le x have hnhi : x < (n : ℝ) + 1 := Int.lt_floor_add_one x have hstart : (ivStart o : Int) ≤ n := by apply Int.le_floor.mpr exact_mod_cast hxlo by_cases heq : x = (n : ℝ) · have hend : n ≤ (ivEnd o : Int) := by have : (n : ℝ) ≤ (ivEnd o : ℝ) := by linarith exact_mod_cast this obtain ⟨i, hi, hleft, hright⟩ := sample (2*n) (by omega) (by omega) have hleft' : ivStartI i ≤ n := by omega have hright' : n ≤ ivEndI i := by omega refine ⟨i, hi, ?_, ?_⟩ · have : (ivStartI i : ℝ) ≤ (n : ℝ) := by exact_mod_cast hleft' linarith · have : (n : ℝ) ≤ (ivEndI i : ℝ) := by exact_mod_cast hright' linarith · have hnx : (n : ℝ) < x := lt_of_le_of_ne hnlo (Ne.symm heq) have hend : n < (ivEnd o : Int) := by have : (n : ℝ) < (ivEnd o : ℝ) := by linarith exact_mod_cast this obtain ⟨i, hi, hleft, hright⟩ := sample (2*n+1) (by omega) (by omega) have hleft' : ivStartI i ≤ n := by omega have hright' : n + 1 ≤ ivEndI i := by omega refine ⟨i, hi, ?_, ?_⟩ · have : (ivStartI i : ℝ) ≤ (n : ℝ) := by exact_mod_cast hleft' linarith · have : (n : ℝ) + 1 ≤ (ivEndI i : ℝ) := by exact_mod_cast hright' linarith · intro hu k hk have hkn : k + 2 * ivStart o ≤ 2 * ivEnd o := by omega have hkR : (k : ℝ) + 2 * (ivStart o : ℝ) ≤ 2 * (ivEnd o : ℝ) := by exact_mod_cast hkn have hk0 : (0 : ℝ) ≤ k := Nat.cast_nonneg k obtain ⟨i, hi, hil, hir⟩ := hu ((ivStart o : ℝ) + (k : ℝ) / 2) ⟨by linarith, by linarith⟩ refine ⟨i, hi, ?_, ?_⟩ · have : 2 * (ivStartI i : ℝ) ≤ 2 * (ivStart o : ℝ) + (k : ℝ) := by linarith exact_mod_cast this · have : 2 * (ivStart o : ℝ) + (k : ℝ) ≤ 2 * (ivEndI i : ℝ) := by linarith exact_mod_cast this /-- On valid input the checker accepts exactly the specified outputs. -/ theorem mergeIntervals_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : mergeIntervals_check input result ↔ mergeIntervals_spec input result := by exact root_of_bridges union_bridge input result /-! ### Implementation helpers -/ /-- Convert an integer endpoint interval to a natural endpoint interval. -/ def toOutputInterval (iv : List Int) : List Nat := [(ivStartI iv).toNat, (ivEndI iv).toNat] /-- Extend the current merged interval with `next`, or start a new block. -/ def mergeStep (current : List Nat) (next : List Int) : List Nat := if ivStartI next ≤ (ivEnd current : Int) then [ivStart current, Nat.max (ivEnd current) (ivEndI next).toNat] else toOutputInterval next /-! ### Main algorithm (impl) -/ /-- Merge intervals by sorting starts and scanning for overlapping runs. -/ def mergeOverlappingIntervals (intervals : Input) : Output := let sorted := intervals.mergeSort fun a b => decide (ivStartI a ≤ ivStartI b) match sorted with | [] => [] | first :: rest => (rest.foldl (fun acc iv => match acc with | [] => [toOutputInterval iv] | current :: earlier => let stepped := mergeStep current iv if ivStartI iv ≤ (ivEnd current : Int) then stepped :: earlier else stepped :: current :: earlier) [toOutputInterval first]).reverse /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem mergeOverlappingIntervals_correct (input : Input) (h : isValidInput input) : mergeIntervals_spec input (mergeOverlappingIntervals input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput [[1, 4], [4, 5]] #guard isValidInput [[1, 4], [2, 3]] #guard isValidInput [[1, 10], [2, 6], [9, 12]] /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput []) #guard !(isValidInput [[1]]) #guard !(isValidInput [[-1, 3]]) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard mergeIntervals_check [[1, 4], [4, 5]] [[1, 5]] #guard mergeIntervals_check [[1, 4], [2, 3]] [[1, 4]] #guard mergeIntervals_check [[1, 10], [2, 6], [9, 12]] [[1, 12]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(mergeIntervals_check [[1, 4], [4, 5]] [[1, 4], [4, 5]]) #guard !(mergeIntervals_check [[1, 4], [2, 3]] [[0, 4]]) #guard !(mergeIntervals_check [[1, 10], [2, 6], [9, 12]] [[1, 11]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard mergeOverlappingIntervals [[1, 4], [4, 5]] == [[1, 5]] #guard mergeOverlappingIntervals [[1, 4], [2, 3]] == [[1, 4]] #guard mergeOverlappingIntervals [[1, 10], [2, 6], [9, 12]] == [[1, 12]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard mergeIntervals_check [[1, 4], [4, 5]] (mergeOverlappingIntervals [[1, 4], [4, 5]]) #guard mergeIntervals_check [[1, 4], [2, 3]] (mergeOverlappingIntervals [[1, 4], [2, 3]]) #guard mergeIntervals_check [[1, 10], [2, 6], [9, 12]] (mergeOverlappingIntervals [[1, 10], [2, 6], [9, 12]]) end PMergeIntervals