Minimize image processing cost with discount
Company: Citadel
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
##### Question
You have n images. For the i-th image, processing costs filterCost[i] per day and must run from startDay[i] to endDay[i] inclusive. Each day you may optionally apply a discount once: if used, processing all images that day costs discountPrice instead of the sum of their individual costs. Compute the minimum total cost to finish all images, modulo 1 000 000 007.
Quick Answer: This question evaluates a candidate's competence in algorithm design and optimization, including interval-based cost aggregation and modular arithmetic for large-number results within the Coding & Algorithms domain.
You have n images to process. The i-th image costs filterCost[i] per day and must be processed every day from startDay[i] to endDay[i], inclusive. On any day, you may choose to use a special discount at most once: if you use it, the total cost for processing all active images on that day becomes discountPrice instead of the sum of their individual daily costs. Compute the minimum total cost needed to finish all image processing, modulo 1000000007.
Constraints
- 0 <= n <= 200000
- len(startDay) = len(endDay) = len(filterCost) = n
- 1 <= startDay[i] <= endDay[i] <= 1000000000 for each image
- 1 <= filterCost[i], discountPrice <= 1000000000
Examples
Input: ([1, 2], [3, 4], [10, 6], 10)
Expected Output: 36
Explanation: Day 1 costs 10. Days 2 and 3 each have total active cost 16, so using the discount makes each of those days cost 10. Day 4 costs 6. Total = 10 + 10 + 10 + 6 = 36.
Input: ([], [], [], 5)
Expected Output: 0
Explanation: There are no images to process, so the total cost is 0.
Hints
- The choice for one day does not affect any other day. If you know the total active processing cost on a day, that day's contribution is simply min(totalActiveCost, discountPrice).
- Do not iterate through every day. Track how the total active daily cost changes only at startDay[i] and endDay[i] + 1, then sweep through the sorted event days.