Filter Occupied Intervals - Solution & Explanation

Q: Is Filter Occupied Intervals easy or hard?

Filter Occupied Intervals is generally considered a medium difficulty problem. The challenge lies in recognizing the interval pattern and choosing the correct ordering strategy. Once intervals are sorted, the filtering logic becomes straightforward.

Q: Filter Occupied Intervals Python/Java solution

Most Python or Java implementations first sort the intervals using the built-in sort function with a comparator on the start time. Then a loop scans through the sorted list while maintaining the last valid interval and applying overlap rules. This pattern keeps the implementation concise and efficient.

Q: How to solve Filter Occupied Intervals in O(n)?

Pure O(n) solutions are only possible if the intervals are already sorted by start time. In that case, iterate through the intervals once while tracking the last active end boundary. Overlaps can be detected and filtered during the same pass without additional sorting.

Q: What is the best approach for Filter Occupied Intervals?

The most common solution sorts intervals by start time and then performs a single pass to filter or merge overlaps. Sorting reduces repeated comparisons and allows detection of conflicts using only the previous interval. This approach runs in O(n log n) time due to sorting and O(1) extra space in most implementations.

Q: Is Filter Occupied Intervals asked at Google/Amazon/Meta?

Interval manipulation problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants such as merging intervals, removing covered intervals, and scheduling conflicts test the same underlying pattern used in Filter Occupied Intervals.

Q: What data structure is used in Filter Occupied Intervals?

The primary structure is an array or list of interval pairs. Many solutions also rely on sorting and simple variables to track the current active interval. More advanced implementations may use event lists or priority queues when applying sweep line techniques.

Q: What is the time complexity of Filter Occupied Intervals?

The optimal approach runs in O(n log n) time because the intervals must be sorted before processing. After sorting, a linear scan processes each interval exactly once. Space complexity is typically O(1) or O(n) depending on whether a new result list is created.

MediumArray Sorting11 min read

Practice this problem

Problem Statement

You are given a 2D integer array occupiedIntervals, where occupiedIntervals[i] = [start_i, end_i] represents a time interval during which you are occupied. Each interval starts at start_i and ends at end_i, 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:

After merging, the occupied intervals are [2, 8], [10, 12], and [14, 16].
Excluding the free interval [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:

After merging, the occupied interval is [1, 5].
Excluding the free interval [3, 8] results in [1, 2].

Constraints:

1 <= occupiedIntervals.length <= 5 * 10⁴
occupiedIntervals[i].length == 2
1 <= start_i <= end_i <= 10⁹
1 <= freeStart <= freeEnd <= 10⁹

Approach Overview

Problem 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.

Solution

We first sort all occupied intervals by their left endpoints, and then traverse all intervals. If the left endpoint of the current interval is greater than the right endpoint of the last interval plus 1, we add the current interval to the result. Otherwise, we merge the current interval with the last interval, and update the right endpoint of the last interval to the larger value of the current interval and the last interval.

Next, we traverse all occupied intervals. If the right endpoint of the current interval is less than the left endpoint of the free interval or the left endpoint of the current interval is greater than the right endpoint of the free interval, we add the current interval to the result. Otherwise, we check if the left endpoint of the current interval is less than the left endpoint of the free interval. If it is, we update the left endpoint of the current interval to the left endpoint of the free interval minus 1, and add it to the result. Then, we check if the right endpoint of the current interval is greater than the right endpoint of the free interval. If it is, we update the right endpoint of the current interval to the right endpoint of the free interval plus 1, and add it to the result.

Finally, we return the result.

The time complexity is O(n log n), and the space complexity is O(n). Where n is the length of the array occupiedIntervals.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

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

Video Solution

3975. Filter Occupied Intervals (Leetcode Medium) • Programming Live with Larry • 254 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Filter Occupied Intervals easy or hard?

Filter Occupied Intervals is generally considered a medium difficulty problem. The challenge lies in recognizing the interval pattern and choosing the correct ordering strategy. Once intervals are sorted, the filtering logic becomes straightforward.

Filter Occupied Intervals Python/Java solution

Most Python or Java implementations first sort the intervals using the built-in sort function with a comparator on the start time. Then a loop scans through the sorted list while maintaining the last valid interval and applying overlap rules. This pattern keeps the implementation concise and efficient.

How to solve Filter Occupied Intervals in O(n)?

Pure O(n) solutions are only possible if the intervals are already sorted by start time. In that case, iterate through the intervals once while tracking the last active end boundary. Overlaps can be detected and filtered during the same pass without additional sorting.

What is the best approach for Filter Occupied Intervals?

The most common solution sorts intervals by start time and then performs a single pass to filter or merge overlaps. Sorting reduces repeated comparisons and allows detection of conflicts using only the previous interval. This approach runs in O(n log n) time due to sorting and O(1) extra space in most implementations.

Is Filter Occupied Intervals asked at Google/Amazon/Meta?

Interval manipulation problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants such as merging intervals, removing covered intervals, and scheduling conflicts test the same underlying pattern used in Filter Occupied Intervals.

What data structure is used in Filter Occupied Intervals?

The primary structure is an array or list of interval pairs. Many solutions also rely on sorting and simple variables to track the current active interval. More advanced implementations may use event lists or priority queues when applying sweep line techniques.

What is the time complexity of Filter Occupied Intervals?

The optimal approach runs in O(n log n) time because the intervals must be sorted before processing. After sorting, a linear scan processes each interval exactly once. Space complexity is typically O(1) or O(n) depending on whether a new result list is created.

Ready to solve this problem?

Practice Filter Occupied Intervals with our built-in code editor and test cases.

Practice on FleetCode

Two Sum

Median of Two Sorted Arrays

Problem Info

DifficultyMedium

Acceptance46.0%

Approaches1

Reading time11 min