Solution

Method 1 - Sweep line algorithm

The key idea for solving this problem is to merge intervals based on the colors applied and create new non-overlapping intervals with their mixed color sums:

Use sweep line and sort events to determine the intervals where color changes.
Events represent a starting or ending of a segment. For each segment [start, end, color], you add two events:
- A start event for start with color.
- An end event for end to remove

Related Tags