101
0/320
Loading content...
You are managing a scheduling system for n time slots, numbered sequentially from 1 to n.
You are given a list of reservations, where each reservation is represented as a triplet [startSlot, endSlot, quantity]. This indicates that a quantity of quantity units has been reserved for every time slot in the range from startSlot to endSlot (inclusive).
Your task is to compute an array result of length n, where result[i] represents the total quantity of reservations that cover time slot i + 1 (using 1-based indexing for the slots).
Key Insight: A naive approach that iterates through each reservation and updates every slot in its range would be inefficient for large inputs. The challenge is to efficiently aggregate overlapping ranges without explicitly iterating through each slot covered by each reservation.
reservations = [[1,2,10],[2,3,20],[2,5,25]]
n = 5[10,55,45,25,25]Let's trace through each time slot: • Slot 1: Only reservation [1,2,10] covers it → Total = 10 • Slot 2: All three reservations cover it → 10 + 20 + 25 = 55 • Slot 3: Reservations [2,3,20] and [2,5,25] cover it → 20 + 25 = 45 • Slot 4: Only reservation [2,5,25] covers it → Total = 25 • Slot 5: Only reservation [2,5,25] covers it → Total = 25
Time Slot Labels: 1 2 3 4 5 Reservation 1: 10 10 Reservation 2: 20 20 Reservation 3: 25 25 25 25 ───────────────────────────────────────────── Totals: 10 55 45 25 25
reservations = [[1,2,10],[2,2,15]]
n = 2[10,25]• Slot 1: Only reservation [1,2,10] covers it → Total = 10 • Slot 2: Both reservations cover it → 10 + 15 = 25
Time Slot Labels: 1 2 Reservation 1: 10 10 Reservation 2: 15 ───────────────────────────── Totals: 10 25
reservations = [[1,3,5]]
n = 3[5,5,5]With a single reservation spanning all slots: • Each slot from 1 to 3 receives quantity 5
Time Slot Labels: 1 2 3 Reservation 1: 5 5 5 ──────────────────────────────── Totals: 5 5 5
Constraints