Devise a strategy to minimize the cost of processing n images, where each image requires specific filters applied for a defined time frame, and the cost to apply filters to the ith image is filterCost[i].
Each image must be processed from startDay[i] to endDay[i] (inclusive).
Additionally, there is an exclusive offer to apply filters to all n images at a discounted rate of discountPrice per day.
Your goal is to create an efficient image processing plan that adheres to time constraints and budget considerations, and return the minimum cost modulo 10^9 + 7.
Example
Given n = 3, filterCost = [2, 3, 4], startDay = [1, 1, 2], endDay = [2, 3, 4], and discountPrice = 6.
- Day 1: images
[1, 2], total cost =2 + 3 = 5 - Day 2: images
[1, 2, 3], total cost =2 + 3 + 4 = 9 - Day 3: images
[2, 3], total cost =3 + 4 = 7 - Day 4: images
[3], total cost =4
Applying filters on all images at 6 per day on the 2nd and 3rd day will be optimal. The final cost is 5 + 6 + 6 + 4 = 21.
This problem is a sweep-line interval aggregation task: for each day, the cost is the minimum of the sum of active image filter costs and the discounted daily price. The efficient solution builds start and end events for each interval, sorts them, and maintains the running total of active costs while accumulating the cost over each time segment. This avoids day-by-day simulation and runs in O(n log n), which is appropriate for large online-assessment constraints.
