You are given a 2D integer array occupiedIntervals, where occupiedIntervals[i] = [starti, endi] represents a time interval during which you are occupied. Each interval starts at starti and ends at endi, inclusive. These intervals may overlap.
You are also given two integers freeStart and freeEnd, which define a free time interval from freeStart to freeEnd, inclusive.
Your task is to merge all occupied intervals that overlap or touch, then remove all integer points in the free interval from the merged occupied intervals.
Two intervals touch if the second interval starts immediately after the first one ends. For example, [1, 1] and [2, 2] touch and should be merged into [1, 2].
Return the remaining occupied intervals in sorted order. The returned intervals must be non-overlapping and must contain the minimum number of intervals possible. If there are no remaining occupied points, return an empty list.
Example 1:
Input: occupiedIntervals = [[2,6],[4,8],[10,10],[10,12],[14,16]], freeStart = 7, freeEnd = 11
Output: [[2,6],[12,12],[14,16]]
Explanation:
[2, 8], [10, 12], and [14, 16].[7, 11] results in [2, 6], [12, 12], and [14, 16].Example 2:
Input: occupiedIntervals = [[1,5],[2,3]], freeStart = 3, freeEnd = 8
Output: [[1,2]]
Explanation:
[1, 5].[3, 8] results in [1, 2].
Constraints:
1 <= occupiedIntervals.length <= 5 * 104occupiedIntervals[i].length == 21 <= starti <= endi <= 1091 <= freeStart <= freeEnd <= 109Problem Overview: You are given a collection of time intervals where each interval represents a range that may already be occupied. The task is to process these ranges and return only the intervals that remain occupied after resolving overlaps or filtering rules defined by the problem.
Approach 1: Brute Force Interval Comparison (O(n²) time, O(1) space)
The most direct method compares every interval with every other interval. For each interval, iterate through the remaining intervals and determine whether it overlaps or is covered. If an interval is completely overlapped or invalid according to the rule set, remove it. This approach relies purely on nested iteration and conditional checks. It works for small inputs but becomes inefficient because each interval may be compared against all others.
Approach 2: Sorting + Interval Filtering (O(n log n) time, O(1) space)
A more efficient strategy sorts intervals by their start time (and sometimes by end time as a tiebreaker). After sorting, iterate once through the array while maintaining the most recent active interval. Because sorted intervals appear in chronological order, you can detect overlap with a simple comparison like current.start <= last_end. Depending on the rule, either merge, discard, or keep the interval. Sorting reduces the need for repeated comparisons and turns the problem into a linear scan after ordering.
Approach 3: Sweep Line Technique (O(n log n) time, O(n) space)
The sweep line approach treats interval boundaries as events. Convert each interval into two events: a start event and an end event. Sort all events and traverse them from left to right while maintaining an active counter. When the counter indicates that a region is occupied, record that range. This technique is common in interval problems and sweep line algorithms because it converts overlapping ranges into a clean linear traversal of events.
Recommended for interviews: The sorting-based interval scan is typically the expected answer. Interviewers want to see that you recognize the structure of an interval processing problem and immediately sort by start time. Brute force demonstrates the baseline understanding, but the sorted linear scan or sweep line approach shows stronger algorithmic reasoning and scales efficiently for large inputs.
Solutions for this problem are being prepared.
Try solving it yourself| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Interval Comparison | O(n²) | O(1) | Small datasets or when simplicity matters more than performance |
| Sorting + Linear Interval Filtering | O(n log n) | O(1) | General case; standard solution for interval problems |
| Sweep Line Technique | O(n log n) | O(n) | Complex interval interactions or when tracking active overlaps is required |
Practice Filter Occupied Intervals with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor