import Mathlib /-! # Task Scheduler You are given an array of CPU tasks, each labeled with a letter from A to Z, and a number n. Each CPU interval can be idle or allow the completion of one task. Tasks can be completed in any order, but there's a constraint: there has to be a gap of at least n intervals between two tasks with the same label. Return the minimum number of CPU intervals required to complete all tasks. ## Constraints - 1 <= tasks.length <= 10^4 - tasks[i] is an uppercase English letter. - 0 <= n <= 100 ## Provided examples - `tasks = ["A"], n = 5` → `1` - `tasks = ["A"], n = 0` → `1` - `tasks = ["A", "B", "C", "D"], n = 0` → `4` ## Synthesized negative examples - invalid input: `tasks = [], n = 0` ([structural] a predicate that admits 1 <= tasks.length <= 10^4. empty list where at least one task is required) - invalid input: `tasks = ["A"], n = 101` ([structural] a predicate that admits 0 <= n <= 100. one past the stated maximum n) - invalid input: `tasks = ["a"], n = 0` ([structural] a predicate that admits tasks[i] is an uppercase English letter.. a predicate checking one alphabetic character accepts lowercase) - `tasks = ["A"], n = 5` → `2` is wrong ([structural] minimality stated as achievability alone. one task plus one idle interval is valid but not minimal) - `tasks = ["A"], n = 0` → `0` is wrong ([structural] no schedule is required to reach the answer. zero intervals complete no tasks; below any achievable count) - `tasks = ["A", "B", "C", "D"], n = 0` → `3` is wrong ([structural] answer computed as one less than the number of tasks. under an off-by-one count, three intervals are accepted.) -/ namespace PTaskScheduler abbrev Input := (List Char) × (Nat) abbrev Output := Nat /-! ### Specification helpers -/ /-- Convert the serialized list of one-character labels to a list of characters. -/ def stringListToCharList (ss : List String) : List Char := ss.map (fun s => s.toList.head?.getD ' ') /-- `sched` completes exactly `tasks`, any two equal labels sitting at least `n + 1` positions apart. -/ def IsValidSchedule (tasks : List Char) (n : Nat) (sched : List (Option Char)) : Prop := (sched.filterMap id).Perm tasks ∧ ∀ i j c, i < j → sched[i]? = some (some c) → sched[j]? = some (some c) → i + (n + 1) ≤ j /-! ### Validity predicate (V) -/ /-- Valid input: 1 to 10^4 tasks, each an uppercase English letter, and n at most 100. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 10 ^ 4 && input.1.all (fun c => 'A' ≤ c && c ≤ 'Z') && input.2 ≤ 100 /-! ### Ideal specification (P_spec) -/ /-- `result` is the least length of any valid schedule for the tasks and gap of `input`. -/ def minimumIntervals_spec (input : Input) (result : Output) : Prop := IsLeast {k | ∃ sched : List (Option Char), IsValidSchedule input.1 input.2 sched ∧ sched.length = k} result /-! ### Decidable specification (P_check) -/ /-- Idle or one of the distinct labels already present in `tasks`. -/ def scheduleAlphabet (tasks : List Char) : List (Option Char) := none :: (tasks.eraseDups.map some) /-- All slot lists of a fixed length over the given finite alphabet. -/ def schedulesOfLength (alphabet : List (Option Char)) : Nat → List (List (Option Char)) | 0 => [[]] | k + 1 => (schedulesOfLength alphabet k).flatMap fun rest => alphabet.map fun slot => slot :: rest /-- Bounded gap check over exactly the in-range positions of `sched`. -/ def gapsRespected (n : Nat) (sched : List (Option Char)) : Bool := (List.finRange sched.length).all fun i => (List.finRange sched.length).all fun j => if i < j then match sched.get i, sched.get j with | some c, some d => if c = d then decide (i.val + (n + 1) ≤ j.val) else true | _, _ => true else true /-- Finite realization of schedule validity for a concrete slot list. -/ def validScheduleFinite (tasks : List Char) (n : Nat) (sched : List (Option Char)) : Bool := decide ((sched.filterMap id).Perm tasks) && gapsRespected n sched /-- Whether some encoded schedule of exactly `len` slots is valid. -/ def existsValidScheduleOfLength (tasks : List Char) (n len : Nat) : Bool := (schedulesOfLength (scheduleAlphabet tasks) len).any fun sched => sched.length == len && validScheduleFinite tasks n sched /-- Executable checker for `minimumIntervals_spec`: attain `result` and exclude every shorter length. -/ def minimumIntervals_check (input : Input) (result : Output) : Bool := existsValidScheduleOfLength input.1 input.2 result && (List.range result).all fun k => !existsValidScheduleOfLength input.1 input.2 k theorem root_of_bridges (bridge : ∀ tasks n k, existsValidScheduleOfLength tasks n k = true ↔ ∃ sched, IsValidSchedule tasks n sched ∧ sched.length = k) (input : Input) (result : Output) : minimumIntervals_check input result ↔ minimumIntervals_spec input result := by simp only [minimumIntervals_check, Bool.and_eq_true, List.all_eq_true, List.mem_range, Bool.not_eq_true', Bool.eq_false_iff, bridge] unfold minimumIntervals_spec IsLeast lowerBounds simp only [Set.mem_setOf_eq] constructor · rintro ⟨ha, hb⟩ exact ⟨ha, fun k hk => Nat.le_of_not_gt (fun hlt => hb k hlt ((bridge _ _ _).mpr hk))⟩ · rintro ⟨ha, hb⟩ exact ⟨ha, fun k hlt hk => (Nat.not_lt_of_ge (hb ((bridge _ _ _).mp hk))) hlt⟩ theorem gaps_bridge (n : Nat) (sched : List (Option Char)) : gapsRespected n sched = true ↔ ∀ i j c, i < j → sched[i]? = some (some c) → sched[j]? = some (some c) → i + (n + 1) ≤ j := by simp only [gapsRespected, List.all_eq_true, List.mem_finRange, forall_const] constructor · intro h i j c hij hi hj obtain ⟨hi', hic⟩ := List.getElem?_eq_some_iff.mp hi obtain ⟨hj', hjc⟩ := List.getElem?_eq_some_iff.mp hj have hh := h ⟨i, hi'⟩ ⟨j, hj'⟩ simpa [List.get_eq_getElem, hic, hjc, hij] using hh · intro h i j by_cases hij : i < j · cases hi : sched.get i with | none => simp [hij, hi] | some c => cases hj : sched.get j with | none => simp [hij, hi, hj] | some d => by_cases hc : c = d · subst d have hh := h i.val j.val c hij (List.getElem?_eq_some_iff.mpr ⟨i.isLt, hi⟩) (List.getElem?_eq_some_iff.mpr ⟨j.isLt, hj⟩) simpa [hij, hi, hj] using hh · simp [hij, hi, hj, hc] · simp [hij] theorem finite_bridge (tasks : List Char) (n : Nat) (sched : List (Option Char)) : validScheduleFinite tasks n sched = true ↔ IsValidSchedule tasks n sched := by simp only [validScheduleFinite, Bool.and_eq_true, decide_eq_true_eq, gaps_bridge, IsValidSchedule] theorem enumeration_bridge (alphabet : List (Option Char)) (k : Nat) (sched : List (Option Char)) : sched ∈ schedulesOfLength alphabet k ↔ sched.length = k ∧ ∀ slot ∈ sched, slot ∈ alphabet := by induction k generalizing sched with | zero => cases sched <;> simp [schedulesOfLength] | succ k ih => cases sched with | nil => simp [schedulesOfLength] | cons x xs => simp [schedulesOfLength, List.mem_flatMap, List.mem_map, ih] grind only [] theorem alphabet_bridge (tasks : List Char) (n : Nat) (sched : List (Option Char)) (h : IsValidSchedule tasks n sched) : ∀ slot ∈ sched, slot ∈ scheduleAlphabet tasks := by intro slot hs cases slot with | none => simp [scheduleAlphabet] | some c => have hc : c ∈ sched.filterMap id := List.mem_filterMap.mpr ⟨some c, hs, rfl⟩ have ht : c ∈ tasks := h.1.mem_iff.mp hc simpa [scheduleAlphabet] using ht theorem exists_bridge (tasks : List Char) (n k : Nat) : existsValidScheduleOfLength tasks n k = true ↔ ∃ sched, IsValidSchedule tasks n sched ∧ sched.length = k := by simp only [existsValidScheduleOfLength, List.any_eq_true, Bool.and_eq_true, beq_iff_eq, finite_bridge, enumeration_bridge] constructor · rintro ⟨sched, ⟨hlen, _⟩, _, hv⟩ exact ⟨sched, hv, hlen⟩ · rintro ⟨sched, hv, hlen⟩ exact ⟨sched, ⟨hlen, alphabet_bridge tasks n sched hv⟩, hlen, hv⟩ /-- On valid input the checker accepts exactly the specified outputs. -/ theorem minimumIntervals_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : minimumIntervals_check input result ↔ minimumIntervals_spec input result := by exact root_of_bridges exists_bridge input result /-! ### Implementation helpers -/ /-- One occurrence count in `tasks` per uppercase label 'A' through 'Z'. -/ def labelCounts (tasks : List Char) : List Nat := "ABCDEFGHIJKLMNOPQRSTUVWXYZ".toList.map fun c => tasks.count c /-- The largest count in the list paired with the number of entries attaining it. -/ def maxFrequencyAndTies (counts : List Nat) : Nat × Nat := counts.foldl (fun acc c => if acc.1 < c then (c, 1) else if acc.1 = c then (acc.1, acc.2 + 1) else acc) (0, 0) /-! ### Main algorithm (impl) -/ /-- Minimum intervals by the frequency formula: with M the largest label count and T the number of labels attaining it, the answer is max(tasks.length, (M - 1) * (n + 1) + T). -/ def leastIntervals (input : Input) : Output := let counts := labelCounts input.1 let (m, t) := maxFrequencyAndTies counts Nat.max input.1.length ((m - 1) * (input.2 + 1) + t) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem leastIntervals_correct (input : Input) (h : isValidInput input) : minimumIntervals_spec input (leastIntervals input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput (stringListToCharList ["A"], 5) #guard isValidInput (stringListToCharList ["A"], 0) #guard isValidInput (stringListToCharList ["A", "B", "C", "D"], 0) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput (stringListToCharList [], 0)) #guard !(isValidInput (stringListToCharList ["A"], 101)) #guard !(isValidInput (stringListToCharList ["a"], 0)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard minimumIntervals_check (stringListToCharList ["A"], 5) 1 #guard minimumIntervals_check (stringListToCharList ["A"], 0) 1 #guard minimumIntervals_check (stringListToCharList ["A", "B", "C", "D"], 0) 4 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(minimumIntervals_check (stringListToCharList ["A"], 5) 2) #guard !(minimumIntervals_check (stringListToCharList ["A"], 0) 0) #guard !(minimumIntervals_check (stringListToCharList ["A", "B", "C", "D"], 0) 3) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard leastIntervals (stringListToCharList ["A"], 5) == 1 #guard leastIntervals (stringListToCharList ["A"], 0) == 1 #guard leastIntervals (stringListToCharList ["A", "B", "C", "D"], 0) == 4 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard minimumIntervals_check (stringListToCharList ["A"], 5) (leastIntervals (stringListToCharList ["A"], 5)) #guard minimumIntervals_check (stringListToCharList ["A"], 0) (leastIntervals (stringListToCharList ["A"], 0)) #guard minimumIntervals_check (stringListToCharList ["A", "B", "C", "D"], 0) (leastIntervals (stringListToCharList ["A", "B", "C", "D"], 0)) end PTaskScheduler