Let's discuss the "Remove Interval" problem. This problem asks us to remove the intersection of a given interval from a list of intervals.

Naive Solution

A brute-force solution would involve iterating through the list of intervals and checking for overlap with the interval to be removed. If an interval overlaps, we'd need to determine the parts of the interval that remain after the removal and add those parts to a result list. This approach directly implements the problem description.

Here's how you can think about the naive approach:

1. Initialization: Create an empty list to store the resulting intervals.
2. Iteration: Iterate through each interval in the input list.
3. Overlap Check: For each interval, check if it overlaps with the toBeRemoved interval.
4. No Overlap: If there is no overlap, add the original interval to the result list.
5. Overlap: If there is an overlap, calculate the remaining parts of the interval after removing the overlapping portion. Add these remaining parts as new intervals to the result list.

Optimal Solution

The optimal solution follows a similar logic to the naive approach but focuses on clear and concise implementation to avoid unnecessary computations.

1. Initialization: Create an empty list to store the resulting intervals.
2. Iteration: Iterate through each interval in the input list.
3. Cases: Check different overlap scenarios:
   • The current interval is completely to the left of toBeRemoved. Add the current interval to the result.
   • The current interval is completely to the right of toBeRemoved. Add the current interval to the result.
   • The current interval overlaps with toBeRemoved. Calculate the non-overlapping portions and add them to the result.

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
        List<List<Integer>> result = new ArrayList<>();

        for (int[] interval : intervals) {
            int start = interval[0];
            int end = interval[1];
            int removeStart = toBeRemoved[0];
            int removeEnd = toBeRemoved[1];

            if (end <= removeStart || start >= removeEnd) {
                // No overlap
                List<Integer> newInterval = new ArrayList<>();
                newInterval.add(start);
                newInterval.add(end);
                result.add(newInterval);
            } else {
                // Overlap
                if (start < removeStart) {
                    List<Integer> newInterval = new ArrayList<>();
                    newInterval.add(start);
                    newInterval.add(removeStart);
                    result.add(newInterval);
                }
                if (end > removeEnd) {
                    List<Integer> newInterval = new ArrayList<>();
                    newInterval.add(removeEnd);
                    newInterval.add(end);
                    result.add(newInterval);
                }
            }
        }

        return result;
    }
}

Big O Runtime

The runtime complexity is O(n), where n is the number of intervals in the input list. We iterate through each interval once.

Big O Space

The space complexity is O(n) in the worst case, where n is the number of intervals. This happens if none of the intervals overlap with the interval to be removed, and we store all of them in the result list.

Edge Cases

• Empty Input: If the input list of intervals is empty, return an empty list.
• No Overlap: If none of the intervals overlap with the interval to be removed, return the original list of intervals.
• Complete Overlap: If an interval completely overlaps with the interval to be removed, no part of it should be included in the result.
• toBeRemoved is empty: If the toBeRemoved interval has start == end, then no interval is removed and the original list is returned.