The trickiest part is handling partial overlaps during add and remove. For addRange:
Find all intervals overlapping
Compute the union (extend left and right as needed)
Remove old intervals, insert the union For removeRange:
Find all intervals overlapping
For each, trim or split as needed
Update the map Time per operation: where is affected intervals. Amortized since each interval is added/removed once. Time: . Space: .