import Mathlib /-! # Insert Interval You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion. Note that you don't need to modify intervals in-place. You can make a new array and return it. ## Constraints - 0 <= intervals.length <= 10^4 - intervals[i].length == 2 - 0 <= starti <= endi <= 10^5 - intervals is sorted by starti in ascending order. - newInterval.length == 2 - 0 <= start <= end <= 10^5 ## Provided examples - `intervals = [[1, 3], [6, 9]], newInterval = [2, 5]` → `[[1, 5], [6, 9]]` - `intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]` → `[[1, 2], [3, 10], [12, 16]]` - `intervals = [], newInterval = [5, 7]` → `[[5, 7]]` ## Synthesized negative examples - invalid input: `intervals = [[1, 2, 3]], newInterval = [0, 0]` ([structural] a predicate that admits intervals[i].length == 2. extra element passes a length check only requiring at least two) - invalid input: `intervals = [[1, 100001]], newInterval = [0, 0]` ([structural] a predicate that admits 0 <= starti <= endi <= 10^5. one past the stated endi maximum) - invalid input: `intervals = [[3, 5], [1, 2]], newInterval = [0, 0]` ([structural] a predicate that admits intervals is sorted by starti in ascending order.. predicate that assumes sorted order but never checks it accepts) - `intervals = [[1, 3], [6, 9]], newInterval = [2, 5]` → `[[1, 4], [6, 9]]` is wrong ([structural] merged interval endpoint is one short, leaving newInterval's end uncovered. Covers all but endpoint 5 of newInterval) - `intervals = [[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], newInterval = [4, 8]` → `[[1, 2], [3, 9], [12, 16]]` is wrong ([structural] merged interval end is one less than required; exact union not enforced.. covers [3,9] instead of [3,10].) - `intervals = [], newInterval = [5, 7]` → `[[5, 7], [8, 9]]` is wrong ([structural] output may contain intervals not present in input or newInterval. adds an unrelated interval while keeping all required ones.) -/ namespace PInsertInterval abbrev Input := (List (List Nat)) × (List Nat) abbrev Output := List (List Nat) /-! ### Specification helpers -/ /-- Each interval of `l` is a two-element list `[a, b]` with `a ≤ b`, the list is sorted by first coordinate, and consecutive intervals do not overlap. -/ def IsValidIntervalList (l : List (List Nat)) : Prop := (∀ iv ∈ l, iv.length = 2 ∧ iv[0]! ≤ iv[1]!) ∧ l.Pairwise (fun x y => x[0]! ≤ y[0]!) ∧ l.Chain' (fun x y => x[1]! < y[0]!) /-- Rational point `p` lies in the closed interval `[a, b]` that the two-element list `iv` represents. -/ def CoversPoint (p : ℚ) (iv : List Nat) : Prop := iv.length = 2 ∧ (iv[0]! : ℚ) ≤ p ∧ p ≤ (iv[1]! : ℚ) /-- Bool test that every pair of adjacent elements of `l` satisfies `R`. -/ def adjacentAll (R : List Nat → List Nat → Bool) (l : List (List Nat)) : Bool := (l.zipWith R l.tail).all id /-! ### Validity predicate (V) -/ /-- Valid input: bounded two-element intervals sorted by start and non-overlapping, plus a well-formed new interval. -/ def isValidInput (input : Input) : Bool := decide (input.1.length ≤ 10000) && input.1.all (fun iv => iv.length == 2 && decide (iv[0]! ≤ iv[1]!) && decide (iv[1]! ≤ 100000)) && adjacentAll (fun x y => decide (x[0]! ≤ y[0]!)) input.1 && adjacentAll (fun x y => decide (x[1]! < y[0]!)) input.1 && input.2.length == 2 && decide (input.2[0]! ≤ input.2[1]!) && decide (input.2[1]! ≤ 100000) /-! ### Ideal specification (P_spec) -/ /-- `result` is a well-formed sorted non-overlapping interval list covering exactly the points covered by `input.1` together with `input.2`. -/ def insertInterval_spec (input : Input) (result : Output) : Prop := IsValidIntervalList result ∧ ∀ p : ℚ, (∃ iv ∈ result, CoversPoint p iv) ↔ (∃ iv ∈ input.1, CoversPoint p iv) ∨ CoversPoint p input.2 /-! ### Decidable specification (P_check) -/ /-- The rational endpoints `iv[0]!` and `iv[1]!` of every interval in `ivs`. -/ def intervalEndpoints (ivs : List (List Nat)) : List ℚ := ivs.flatMap fun (iv : List Nat) => [(iv[0]! : ℚ), (iv[1]! : ℚ)] /-- Every endpoint of `a` or `b` plus the midpoint of every pair of endpoints. -/ def coverageSamples (a b : List (List Nat)) : List ℚ := let eps := intervalEndpoints a ++ intervalEndpoints b eps ++ eps.flatMap fun x => eps.map fun y => (x + y) / 2 /-- Decidability of `CoversPoint p iv`, obtained by unfolding it to its decidable clauses. -/ instance decidableCoversPoint (p : ℚ) (iv : List Nat) : Decidable (CoversPoint p iv) := inferInstanceAs (Decidable (iv.length = 2 ∧ (iv[0]! : ℚ) ≤ p ∧ p ≤ (iv[1]! : ℚ))) /-- Bool form of `∃ iv ∈ ivs, CoversPoint p iv`. -/ def coversAny (p : ℚ) (ivs : List (List Nat)) : Bool := ivs.any fun iv => decide (CoversPoint p iv) /-- Bool form of `IsValidIntervalList`, using `adjacentAll` for the sorted and non-overlap clauses as `isValidInput` does. -/ def validIntervalListBool (l : List (List Nat)) : Bool := l.all (fun iv => decide (iv.length = 2 ∧ iv[0]! ≤ iv[1]!)) && adjacentAll (fun x y => decide (x[0]! ≤ y[0]!)) l && adjacentAll (fun x y => decide (x[1]! < y[0]!)) l /-- Executable checker for `insertInterval_spec`: well-formedness of `result` plus coverage agreement at every sample point. -/ def insertInterval_check (input : Input) (result : Output) : Bool := validIntervalListBool result && (coverageSamples result (input.1 ++ [input.2])).all fun p => coversAny p result == (coversAny p input.1 || decide (CoversPoint p input.2)) theorem root_of_bridges (vb : ∀ l, validIntervalListBool l = true ↔ IsValidIntervalList l) (cb : ∀ a b : List (List Nat), (∀ p ∈ coverageSamples a b, (∃ iv ∈ a, CoversPoint p iv) ↔ (∃ iv ∈ b, CoversPoint p iv)) → ∀ p, (∃ iv ∈ a, CoversPoint p iv) ↔ (∃ iv ∈ b, CoversPoint p iv)) (input : Input) (result : Output) : insertInterval_check input result ↔ insertInterval_spec input result := by simp only [insertInterval_check, Bool.and_eq_true, vb, List.all_eq_true, beq_iff_eq, insertInterval_spec] have cv : ∀ p l, coversAny p l = true ↔ ∃ iv ∈ l, CoversPoint p iv := by intro p l simp [coversAny] constructor · rintro ⟨hv, hs⟩ refine ⟨hv, ?_⟩ have hh := cb result (input.1 ++ [input.2]) (by intro p hp have he := hs p hp have : (coversAny p result = true) ↔ (coversAny p input.1 || decide (CoversPoint p input.2)) = true := by rw [he] simpa [cv] using this) simpa using hh · rintro ⟨hv, hs⟩ refine ⟨hv, ?_⟩ intro p hp apply Bool.eq_iff_iff.mpr simpa [cv] using hs p lemma adjacent_bridge (R : List Nat → List Nat → Prop) [DecidableRel R] (l : List (List Nat)) : adjacentAll (fun x y => decide (R x y)) l = true ↔ l.IsChain R := by induction l with | nil => simp [adjacentAll] | cons x xs ih => cases xs with | nil => simp [adjacentAll] | cons y ys => simpa [adjacentAll, List.isChain_cons_cons] using (and_congr (show decide (R x y) = true ↔ R x y from by simp) ih) lemma valid_bridge (l : List (List Nat)) : validIntervalListBool l = true ↔ IsValidIntervalList l := by let R : List Nat → List Nat → Prop := fun x y => x[0]! ≤ y[0]! letI : Trans R R R := ⟨fun h1 h2 => Nat.le_trans h1 h2⟩ have hh : l.IsChain R ↔ l.Pairwise R := List.isChain_iff_pairwise simp only [validIntervalListBool, IsValidIntervalList, Bool.and_eq_true, List.all_eq_true, decide_eq_true_eq, adjacent_bridge, and_assoc] change (_ ∧ l.IsChain R ∧ _) ↔ (_ ∧ l.Pairwise R ∧ _) rw [hh] rfl lemma root_with_validity (cb : ∀ a b : List (List Nat), (∀ p ∈ coverageSamples a b, (∃ iv ∈ a, CoversPoint p iv) ↔ (∃ iv ∈ b, CoversPoint p iv)) → ∀ p, (∃ iv ∈ a, CoversPoint p iv) ↔ (∃ iv ∈ b, CoversPoint p iv)) (input : Input) (result : Output) : insertInterval_check input result ↔ insertInterval_spec input result := root_of_bridges valid_bridge cb input result lemma midpoint_profile (eps : List ℚ) (p l r : ℚ) (hl : l ∈ eps) (hr : r ∈ eps) (hlp : l ≤ p) (hpr : p ≤ r) : ∃ q ∈ eps ++ eps.flatMap (fun x => eps.map (fun y => (x + y) / 2)), ∀ x ∈ eps, (x ≤ p ↔ x ≤ q) ∧ (p ≤ x ↔ q ≤ x) := by let lower : Finset ℚ := (eps.filter fun x => x ≤ p).toFinset let upper : Finset ℚ := (eps.filter fun x => p ≤ x).toFinset have hlower : lower.Nonempty := by refine ⟨l, ?_⟩ simp [lower, hl, hlp] have hupper : upper.Nonempty := by refine ⟨r, ?_⟩ simp [upper, hr, hpr] let lo : ℚ := lower.max' hlower let hi : ℚ := upper.min' hupper have hlo_mem : lo ∈ lower := Finset.max'_mem lower hlower have hhi_mem : hi ∈ upper := Finset.min'_mem upper hupper have hlo_eps : lo ∈ eps := by exact (by simpa [lower] using hlo_mem : lo ∈ eps ∧ lo ≤ p).1 have hhi_eps : hi ∈ eps := by exact (by simpa [upper] using hhi_mem : hi ∈ eps ∧ p ≤ hi).1 have hlo_p : lo ≤ p := by exact (by simpa [lower] using hlo_mem : lo ∈ eps ∧ lo ≤ p).2 have hp_hi : p ≤ hi := by exact (by simpa [upper] using hhi_mem : hi ∈ eps ∧ p ≤ hi).2 refine ⟨(lo + hi) / 2, ?_, ?_⟩ · exact List.mem_append.mpr (Or.inr (List.mem_flatMap.mpr ⟨lo, hlo_eps, List.mem_map.mpr ⟨hi, hhi_eps, rfl⟩⟩)) · intro x hx constructor · constructor · intro hxp have hxlo : x ≤ lo := lower.le_max' x (by simp [lower, hx, hxp]) linarith · intro hxq by_contra hnxp have hpx : p < x := lt_of_not_ge hnxp have hhix : hi ≤ x := upper.min'_le x (by simp [upper, hx, hpx.le]) linarith · constructor · intro hpx have hhix : hi ≤ x := upper.min'_le x (by simp [upper, hx, hpx]) linarith · intro hqx by_contra hnpx have hxp : x < p := lt_of_not_ge hnpx have hxlo : x ≤ lo := lower.le_max' x (by simp [lower, hx, hxp.le]) linarith lemma coverage_profile (a b : List (List Nat)) (p : ℚ) (iv : List Nat) (hi : iv ∈ a ++ b) (hp : CoversPoint p iv) : ∃ q ∈ coverageSamples a b, ∀ j ∈ a ++ b, CoversPoint p j ↔ CoversPoint q j := by let eps := intervalEndpoints a ++ intervalEndpoints b have endpoints : ∀ j ∈ a ++ b, (j[0]! : ℚ) ∈ eps ∧ (j[1]! : ℚ) ∈ eps := by intro j hj have hh : ∀ c : List (List Nat), j ∈ c → (j[0]! : ℚ) ∈ intervalEndpoints c ∧ (j[1]! : ℚ) ∈ intervalEndpoints c := by intro c hc constructor · exact List.mem_flatMap.mpr ⟨j, hc, by simp⟩ · exact List.mem_flatMap.mpr ⟨j, hc, by simp⟩ rcases List.mem_append.mp hj with hj | hj · exact ⟨List.mem_append.mpr (Or.inl (hh a hj).1), List.mem_append.mpr (Or.inl (hh a hj).2)⟩ · exact ⟨List.mem_append.mpr (Or.inr (hh b hj).1), List.mem_append.mpr (Or.inr (hh b hj).2)⟩ obtain ⟨q, hq, hcmp⟩ := midpoint_profile eps p (iv[0]! : ℚ) (iv[1]! : ℚ) (endpoints iv hi).1 (endpoints iv hi).2 hp.2.1 hp.2.2 refine ⟨q, ?_, ?_⟩ · simpa only [coverageSamples, eps] using hq · intro j hj exact and_congr Iff.rfl (and_congr (hcmp _ (endpoints j hj).1).1 (hcmp _ (endpoints j hj).2).2) lemma coverage_bridge (a b : List (List Nat)) (hs : ∀ p ∈ coverageSamples a b, (∃ iv ∈ a, CoversPoint p iv) ↔ (∃ iv ∈ b, CoversPoint p iv)) : ∀ p, (∃ iv ∈ a, CoversPoint p iv) ↔ (∃ iv ∈ b, CoversPoint p iv) := by intro p constructor · rintro ⟨iv, hiv, hcov⟩ obtain ⟨q, hq, hcmp⟩ := coverage_profile a b p iv (List.mem_append.mpr (Or.inl hiv)) hcov have hqa : ∃ j ∈ a, CoversPoint q j := ⟨iv, hiv, (hcmp iv (List.mem_append.mpr (Or.inl hiv))).mp hcov⟩ obtain ⟨j, hj, hqj⟩ := (hs q hq).mp hqa exact ⟨j, hj, (hcmp j (List.mem_append.mpr (Or.inr hj))).mpr hqj⟩ · rintro ⟨iv, hiv, hcov⟩ obtain ⟨q, hq, hcmp⟩ := coverage_profile a b p iv (List.mem_append.mpr (Or.inr hiv)) hcov have hqb : ∃ j ∈ b, CoversPoint q j := ⟨iv, hiv, (hcmp iv (List.mem_append.mpr (Or.inr hiv))).mp hcov⟩ obtain ⟨j, hj, hqj⟩ := (hs q hq).mpr hqb exact ⟨j, hj, (hcmp j (List.mem_append.mpr (Or.inl hj))).mpr hqj⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem insertInterval_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : insertInterval_check input result ↔ insertInterval_spec input result := by exact root_with_validity coverage_bridge input result /-! ### Implementation helpers -/ /-- Recursive worker: `acc` holds the placed intervals in reverse, `cur` the interval being merged, and the last argument the unprocessed suffix. -/ def go (acc : List (List Nat)) (cur : List Nat) : List (List Nat) → List (List Nat) | [] => acc.reverse ++ [cur] | iv :: rest => if iv[1]! < cur[0]! then go (iv :: acc) cur rest else if cur[1]! < iv[0]! then acc.reverse ++ cur :: iv :: rest else go acc [min cur[0]! iv[0]!, max cur[1]! iv[1]!] rest /-! ### Main algorithm (impl) -/ /-- Insertion by a single linear scan: intervals strictly before the new one are kept, overlapping ones are merged into it, and the remainder is appended. -/ def insertIntervalImpl (input : Input) : Output := go [] input.2 input.1 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem insertIntervalImpl_correct (input : Input) (h : isValidInput input) : insertInterval_spec input (insertIntervalImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ([[1, 3], [6, 9]], [2, 5]) #guard isValidInput ([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) #guard isValidInput ([], [5, 7]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ([[1, 2, 3]], [0, 0])) #guard !(isValidInput ([[1, 100001]], [0, 0])) #guard !(isValidInput ([[3, 5], [1, 2]], [0, 0])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard insertInterval_check ([[1, 3], [6, 9]], [2, 5]) [[1, 5], [6, 9]] #guard insertInterval_check ([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) [[1, 2], [3, 10], [12, 16]] #guard insertInterval_check ([], [5, 7]) [[5, 7]] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(insertInterval_check ([[1, 3], [6, 9]], [2, 5]) [[1, 4], [6, 9]]) #guard !(insertInterval_check ([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) [[1, 2], [3, 9], [12, 16]]) #guard !(insertInterval_check ([], [5, 7]) [[5, 7], [8, 9]]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard insertIntervalImpl ([[1, 3], [6, 9]], [2, 5]) == [[1, 5], [6, 9]] #guard insertIntervalImpl ([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) == [[1, 2], [3, 10], [12, 16]] #guard insertIntervalImpl ([], [5, 7]) == [[5, 7]] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard insertInterval_check ([[1, 3], [6, 9]], [2, 5]) (insertIntervalImpl ([[1, 3], [6, 9]], [2, 5])) #guard insertInterval_check ([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8]) (insertIntervalImpl ([[1, 2], [3, 5], [6, 7], [8, 10], [12, 16]], [4, 8])) #guard insertInterval_check ([], [5, 7]) (insertIntervalImpl ([], [5, 7])) end PInsertInterval