Non-overlapping Intervals - Practice Coding Problems

Non-overlapping Intervals - Problem

Given an array of intervals intervals where intervals[i] = [start_i, end_i], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

Note that intervals which only touch at a point are non-overlapping. For example, [1, 2] and [2, 3] are non-overlapping.

Input & Output

Example 1 — Basic Overlap

$ Input: intervals = [[1,2],[2,3],[3,4],[1,3]]

› Output: 1

💡 Note: After sorting by end time: [[1,2],[2,3],[1,3],[3,4]]. Keep [1,2], [2,3], [3,4]. Remove [1,3] which overlaps with [1,2].

Example 2 — Multiple Overlaps

$ Input: intervals = [[1,2],[1,2],[1,2]]

› Output: 2

💡 Note: All three intervals are identical and overlap. We can only keep one, so remove 2 intervals.

Example 3 — No Overlaps Needed

$ Input: intervals = [[1,2],[2,3]]

› Output: 0

💡 Note: Intervals [1,2] and [2,3] only touch at point 2, which is considered non-overlapping. No removal needed.

Constraints

1 ≤ intervals.length ≤ 10⁵
intervals[i].length == 2
-5 × 10⁴ ≤ start_i < end_i ≤ 5 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array of intervals with potential overlaps

Process

Sort by end time and apply greedy selection

Output

Minimum number of intervals to remove

Key Takeaway

🎯 Key Insight: Sort by end time and greedily keep intervals that end earliest to maximize non-overlapping selections

Asked in

G Google 15 a Amazon 12 M Microsoft 8 🍎 Apple 6

The key insight is to use a greedy approach: sort intervals by end time and always keep the interval that ends earliest among overlapping ones. This maximizes the number of intervals we can keep. Best approach is Greedy Sort by End Time with Time: O(n log n), Space: O(1).

Common Approaches

Approach	Time	Space	Notes
✓ Sort by Start Time + Count Overlaps	O(n log n)	O(1)	Sort by start time and count overlapping intervals to remove
Brute Force - Try All Combinations	O(2ⁿ × n)	O(n)	Generate all possible subsets and find the largest non-overlapping one
Greedy - Sort by End Time	O(n log n)	O(1)	Sort intervals by end time and greedily select non-overlapping ones

Sort by Start Time + Count Overlaps — Algorithm Steps

Sort intervals by start time
Iterate through sorted intervals
When overlap detected, remove interval with later end time
Count total removals needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Sort

Sort intervals by start time

Scan

Check adjacent intervals for overlaps

Remove

Remove interval with later end time

Count

Return total removals needed

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int compareByStart(const void* a, const void* b) {
    int* intervalA = (int*)a;
    int* intervalB = (int*)b;
    return intervalA[0] - intervalB[0]; // Sort by start time
}

int solution(int intervals[][2], int n) {
    if (n == 0) return 0;
    
    // Sort intervals by start time
    qsort(intervals, n, sizeof(intervals[0]), compareByStart);
    
    int removeCount = 0;
    int i = 0;
    
    while (i < n - 1) {
        // Check if current and next interval overlap
        if (intervals[i][1] > intervals[i + 1][0]) {
            // Overlap detected - remove the one with later end time
            removeCount++;
            if (intervals[i][1] > intervals[i + 1][1]) {
                // Remove current interval (keep next)
                intervals[i][0] = intervals[i + 1][0];
                intervals[i][1] = intervals[i + 1][1];
            }
            // If we remove next interval, just continue with current
        }
        i++;
    }
    
    return removeCount;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [[a,b],[c,d]] format
    int intervals[1000][2];
    int n = 0;
    char* ptr = line + 1; // Skip first [
    
    while (*ptr && *ptr != ']' || *(ptr+1) == ',') {
        if (*ptr == '[') {
            ptr++;
            intervals[n][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            intervals[n][1] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            n++;
        } else {
            ptr++;
        }
    }
    
    int result = solution(intervals, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n)

Sorting takes O(n log n), then single pass through intervals takes O(n)

⚡ Linearithmic

Space Complexity

O(1)

Only using constant extra variables, sorting is in-place

✓ Linear Space

89.4K Views

High Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sort by Start Time + Count Overlaps — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler