import Mathlib /-! # Corporate Flight Bookings There are n flights that are labeled from 1 to n. You are given an array of flight bookings bookings, where bookings[i] = [first_i, last_i, seats_i] represents a booking for flights first_i through last_i (inclusive) with seats_i seats reserved for each flight in the range. Return an array answer of length n, where answer[i] is the total number of seats reserved for flight i + 1 (0 <= i < n). ## Constraints - 1 <= n <= 2 * 10^4 - 1 <= bookings.length <= 2 * 10^4 - bookings[i].length == 3 - 1 <= first_i <= last_i <= n - 1 <= seats_i <= 10^4 ## Provided examples - `bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]], n = 5` → `[10, 55, 45, 25, 25]` - `bookings = [[1, 2, 10], [2, 2, 15]], n = 2` → `[10, 25]` - `bookings = [[1, 2, 1], [1, 2, 1], [1, 2, 1]], n = 2` → `[3, 3]` ## Synthesized negative examples - invalid input: `bookings = [[1, 1, 1]], n = 20001` ([structural] a predicate that admits 1 <= n <= 2 * 10^4. one past the stated maximum n) - invalid input: `bookings = [], n = 1` ([structural] a predicate that admits 1 <= bookings.length <= 2 * 10^4. empty bookings where at least one booking is required) - invalid input: `bookings = [[1, 2, 10, 5]], n = 2` ([structural] a predicate that admits bookings[i].length == 3. extra fourth element; a predicate checking seats but not exact length accepts it) - `bookings = [[1, 2, 10], [2, 3, 20], [2, 5, 25]], n = 5` → `[10, 45, 25, 25, 0]` is wrong ([structural] upper bound treated as exclusive. range upper bound is exclusive) - `bookings = [[1, 2, 10], [2, 2, 15]], n = 2` → `[10, 0]` is wrong ([structural] range upper bound treated as exclusive. Treats last as exclusive, so [2,2] covers nothing.) - `bookings = [[1, 2, 1], [1, 2, 1], [1, 2, 1]], n = 2` → `[0, 3]` is wrong ([structural] lower range endpoint is exclusive rather than inclusive. bookings contribute to flight 2 only) -/ namespace PCorporateFlightBookings abbrev Input := (Nat) × (List (List Nat)) abbrev Output := List Nat /-! ### Specification helpers -/ /-- `b` is the booking triple `[first, last, seats]`. -/ def IsBooking (b : List Nat) (first last seats : Nat) : Prop := b = [first, last, seats] /-- The seats booking `b` contributes to `flight`, or nothing if it does not cover it. -/ def coversFlight (b : List Nat) (flight : Nat) : Option Nat := match b with | [first, last, seats] => if b = [first, last, seats] ∧ first ≤ flight ∧ flight ≤ last then some seats else none | _ => none /-! ### Validity predicate (V) -/ /-- Valid input: positive `n` and `bookings.length` within bounds, every booking a triple `[first, last, seats]` with `1 ≤ first ≤ last ≤ n` and `1 ≤ seats ≤ 10^4`. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1 && input.1 ≤ 2 * 10^4 && 1 ≤ input.2.length && input.2.length ≤ 2 * 10^4 && input.2.all (fun b => b.length = 3) && input.2.all (fun b => match b with | [first, last, seats] => 1 ≤ first && first ≤ last && last ≤ input.1 && 1 ≤ seats && seats ≤ 10^4 | _ => false) /-! ### Ideal specification (P_spec) -/ /-- `result` has exactly `n` entries, and for every index `i < n` its entry is the total seats reserved for flight `i + 1`, summed with multiplicity over all covering bookings. -/ def corpFlightBookings_spec (input : Input) (result : Output) : Prop := result.length = input.1 ∧ ∀ i : Nat, i < input.1 → result[i]? = some ((input.2.filterMap fun b => coversFlight b (i + 1)).sum) /-! ### Decidable specification (P_check) -/ /-- Executable checker obtained mechanically from the specification. -/ def corpFlightBookings_check (input : Input) (result : Output) : Bool := @decide (corpFlightBookings_spec input result) (by unfold corpFlightBookings_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem corpFlightBookings_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : corpFlightBookings_check input result ↔ corpFlightBookings_spec input result := by simp [corpFlightBookings_check] /-! ### Implementation helpers -/ /-- Add one booking's seats at index `first - 1` of the difference array and subtract them after `last`. -/ def applyBooking (n : Nat) (diff : Array Int) (b : List Nat) : Array Int := match b with | [first, last, seats] => let diff := diff.set! (first - 1) (diff[first - 1]! + (seats : Int)) if last < n then diff.set! last (diff[last]! - (seats : Int)) else diff | _ => diff /-- Accumulate the difference array's prefix sums into the list of per-flight seat totals. -/ def prefixToAnswer (diff : Array Int) (n : Nat) : List Nat := ((List.range n).foldl (fun (acc : Int × Array Nat) (i : Nat) => let s : Int := acc.1 + diff[i]! (s, acc.2.push s.toNat)) (0, #[])).2.toList /-! ### Main algorithm (impl) -/ /-- Seat totals per flight by a difference array over the bookings followed by a prefix-sum scan. -/ def corpFlightBookingsImpl (input : Input) : Output := let n := input.1 let diff := input.2.foldl (applyBooking n) (Array.replicate (n + 1) (0 : Int)) prefixToAnswer diff n /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem corpFlightBookingsImpl_correct (input : Input) (h : isValidInput input) : corpFlightBookings_spec input (corpFlightBookingsImpl input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (5, [[1, 2, 10], [2, 3, 20], [2, 5, 25]]) #guard isValidInput (2, [[1, 2, 10], [2, 2, 15]]) #guard isValidInput (2, [[1, 2, 1], [1, 2, 1], [1, 2, 1]]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (20001, [[1, 1, 1]])) #guard !(isValidInput (1, [])) #guard !(isValidInput (2, [[1, 2, 10, 5]])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard corpFlightBookings_check (5, [[1, 2, 10], [2, 3, 20], [2, 5, 25]]) [10, 55, 45, 25, 25] #guard corpFlightBookings_check (2, [[1, 2, 10], [2, 2, 15]]) [10, 25] #guard corpFlightBookings_check (2, [[1, 2, 1], [1, 2, 1], [1, 2, 1]]) [3, 3] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(corpFlightBookings_check (5, [[1, 2, 10], [2, 3, 20], [2, 5, 25]]) [10, 45, 25, 25, 0]) #guard !(corpFlightBookings_check (2, [[1, 2, 10], [2, 2, 15]]) [10, 0]) #guard !(corpFlightBookings_check (2, [[1, 2, 1], [1, 2, 1], [1, 2, 1]]) [0, 3]) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard corpFlightBookingsImpl (5, [[1, 2, 10], [2, 3, 20], [2, 5, 25]]) == [10, 55, 45, 25, 25] #guard corpFlightBookingsImpl (2, [[1, 2, 10], [2, 2, 15]]) == [10, 25] #guard corpFlightBookingsImpl (2, [[1, 2, 1], [1, 2, 1], [1, 2, 1]]) == [3, 3] /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard corpFlightBookings_check (5, [[1, 2, 10], [2, 3, 20], [2, 5, 25]]) (corpFlightBookingsImpl (5, [[1, 2, 10], [2, 3, 20], [2, 5, 25]])) #guard corpFlightBookings_check (2, [[1, 2, 10], [2, 2, 15]]) (corpFlightBookingsImpl (2, [[1, 2, 10], [2, 2, 15]])) #guard corpFlightBookings_check (2, [[1, 2, 1], [1, 2, 1], [1, 2, 1]]) (corpFlightBookingsImpl (2, [[1, 2, 1], [1, 2, 1], [1, 2, 1]])) end PCorporateFlightBookings