Delete a Character From Cover

Problem: Interval-Aware Deletion

You are given a string of length N (initially indices 0 to N-1) and a list of intervals [start, end] (inclusive) representing protected segments of the string. You are also given a list of deletions, where each deletion specifies an index i to remove from the current string. When a character is deleted, the indices of all subsequent characters shift to the left by 1.

Your task is to implement a function that processes these deletions sequentially and returns the final state of the protected intervals. If a deletion index falls within an interval, the interval should be shortened or split accordingly. If the deletion index is outside any protected interval, simply shift the boundaries of the intervals that appear after the deleted index.

Function Signature

def update_intervals(n: int, intervals: List[List[int]], deletions: List[int]) -> List[List[int]]:

Constraints

• n: up to 10^5
• Number of intervals and deletions: up to 10^4
• The string index i provided in deletions refers to the index at the time of the deletion.

Example

• Input: n=10, intervals=[[2, 5], [7, 8]], deletions=[3, 0]
• Step 1 (delete index 3): The interval [2, 5] becomes [2, 4]. The interval [7, 8] shifts to [6, 7].
• Step 2 (delete index 0): The interval [2, 4] shifts to [1, 3]. The interval [6, 7] shifts to [5, 6].
• Output: [[1, 3], [5, 6]]

Edge Cases

• Deleting an index that makes an interval length zero (e.g., [3, 3] becomes empty).
• Multiple deletions in a single interval.
• Deletions occurring before or after all intervals.