## Problem An employee plans a schedule over `n` days. The schedule string contains `W` for a workday and `O` for a day off. Each workday earns `dailyPay`. In addition, a workday earns `consecutiveBonus` when the immediately preceding day is also a workday. You may change at most `k` occurrences of `O` into `W`. Existing workdays cannot be changed. Return the maximum total earnings over the whole schedule. ### Function Contract Implement: ```text maximizeScheduleEarnings(schedule, k, dailyPay, consecutiveBonus) -> integer ``` ### Constraints & Assumptions - `0 <= n <= 200,000` and `len(schedule) = n`. - `schedule` contains only `W` and `O`. - `0 <= k <= n`. - `0 <= dailyPay, consecutiveBonus <= 10^9`. - Earnings and intermediate calculations fit in a signed 64-bit integer. - Changing fewer than `k` days is allowed. Because both payments are nonnegative, changing an available day can never reduce earnings. - Day `0` has no preceding day and therefore cannot receive the consecutive bonus from outside the schedule. ### Clarifying Questions to Ask - Is the bonus paid for every adjacent `WW` pair? Yes; a run of length `r` earns `r * dailyPay + (r - 1) * consecutiveBonus`. - Can a workday be changed back to a day off? No. - Must exactly `k` days be changed? No, at most `k`. - Can pay values be zero? Yes. ```hint Separate base pay from newly created adjacencies Once the number of converted days is known, daily pay is fixed. The remaining decision is which conversions create the most adjacent workday pairs. ``` ```hint Closing an internal gap has an extra benefit Filling every day in an off-day gap between two existing work runs merges the runs and creates one more adjacency than extending from only one side. ``` ### Examples ```text schedule = "WOOW", k = 1 dailyPay = 10, consecutiveBonus = 4 ``` Changing either middle day produces `WWOW` or `WOWW`, for earnings `30 + 4 = 34`. ```text schedule = "WOOW", k = 2 ``` Filling both days produces `WWWW`, for earnings `40 + 12 = 52`. For `schedule = "OOOO"`, `k = 2`, `dailyPay = 5`, and `consecutiveBonus = 3`, place the two new workdays together for `13`. ### Evaluation Focus - Counts every original and converted workday and every resulting adjacent pair exactly once. - Prioritizes fully bridgeable internal gaps appropriately and handles remaining extensions. - Handles no existing workdays, all workdays, `k = 0`, and `k` larger than the number of days off. - Runs in `O(n log n)` time or better with `O(n)` auxiliary space or better. ### Extensions to Discuss 1. What changes if converting day `i` has its own cost? 2. How would negative bonuses affect the “use every available conversion” observation? 3. Can the gap strategy be implemented without sorting when `k` is small?