Non-Overlapping Intervals

Last Updated : 7 Aug, 2025

Given a 2D array intervals[][], where intervals[i] = [starti, endi]. Find the minimum number of intervals need to be removed to make the rest of the intervals non-overlapping.

Note: Two intervals are considered non-overlapping if the end time of one interval is less than or equal to the start time of the next interval.

Examples:

Input: intervals[][] = [[1, 2], [2, 3], [3, 4], [1, 3]]
Output: 1
Explanation: Removal of [1, 3] makes the ranges non-overlapping.
Input: intervals[][] = [[1, 3], [1, 3], [1, 3]]
Output: 2
Explanation: Removal of two occurrences of [1, 3] makes the remaining ranges non-overlapping.
Input: intervals[][] = [[1, 2], [5, 10], [18, 35], [40, 45]]
Output: 0
Explanation: All ranges are already non-overlapping.

Try it on GfG Practice

Table of Content

Sorting by the Starting Values - O(n*log n) Time and O(1) Space
Sorting by the Ending Values - O(n*log n) Time and O(1) Space

[Approach 1] Sorting by the Starting Values - O(n*log n) Time and O(1) Space

The idea is to use a greedy approach to select the interval to be removed, such that removal count is minimized. First we sort the intervals by their starting values. Then traverse through the interval array and check if any interval has a starting point smaller than the ending point of the previous interval (ie. there is an overlap). Incase overlapping occurs remove the interval with greater ending point.

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minRemoval(vector<vector<int>>& intervals) {
  	int cnt = 0;
  
    // Sort by minimum starting point
    sort(intervals.begin(), intervals.end());

    int end = intervals[0][1];
    for (int i = 1; i < intervals.size(); i++) {

        // If the current starting point is less than
        // the previous interval's ending point
        // (ie. there is an overlap)
        if (intervals[i][0] < end) {
          
            // Increase cnt and remove the interval
            // with the higher ending point
          	cnt++;
            end = min(intervals[i][1], end);
        }
      	
      	// Incase of no overlapping, this interval is 
      	// not removed and 'end' will be updated
        else
            end = intervals[i][1];
    }

    return cnt;
}

int main() {
    vector<vector<int> > intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
    cout << minRemoval(intervals) << endl;
}

Java

import java.util.Arrays;

class GfG {
    static int minRemoval(int[][] intervals) {
        int cnt = 0;
      
        // Sort by minimum starting point
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

        int end = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {

            // If the current starting point is less than
            // the previous interval's ending point
            // (ie. there is an overlap)
            if (intervals[i][0] < end) {
              
                // Increase cnt and remove the interval
                // with the higher ending point
                cnt++;
                end = Math.min(intervals[i][1], end);
            }

            // Incase of no overlapping, this interval is 
            // not removed and 'end' will be updated
            else
                end = intervals[i][1];
        }

        return cnt;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1, 2}, {2, 3}, {3, 4}, {1, 3}};
        System.out.println(minRemoval(intervals));
    }
}

Python

def minRemoval(intervals):
    cnt = 0

    # Sort by minimum starting point
    intervals.sort(key=lambda x: x[0])

    end = intervals[0][1]
    for i in range(1, len(intervals)):

        # If the current starting point is less than
        # the previous interval's ending point
        # (ie. there is an overlap)
        if intervals[i][0] < end:
          
            # Increase cnt and remove the interval
            # with the higher ending point
            cnt += 1
            end = min(intervals[i][1], end)

        # Incase of no overlapping, this interval is 
        # not removed and 'end' will be updated
        else:
            end = intervals[i][1]

    return cnt

if __name__ == "__main__":
    intervals = [[1, 2], [2, 3], [3, 4], [1, 3]]
    print(minRemoval(intervals))

C#

using System;
using System.Collections.Generic;

class GfG {
    static int minRemoval(int[][] intervals) {
        int cnt = 0;

        // Sort by minimum starting point
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));

        int end = intervals[0][1];
        for (int i = 1; i < intervals.Length; i++) {

            // If the current starting point is less than
            // the previous interval's ending point
            // (ie. there is an overlap)
            if (intervals[i][0] < end) {
              
                // Increase cnt and remove the interval
                // with the higher ending point
                cnt++;
                end = Math.Min(intervals[i][1], end);
            }

            // Incase of no overlapping, this interval is 
            // not removed and 'end' will be updated
            else
                end = intervals[i][1];
        }

        return cnt;
    }

    static void Main() {
        int[][] intervals = new int[][] { new int[] { 1, 2 }, new int[] { 2, 3 }, new int[] { 3, 4 }, new int[] { 1, 3 } };
        Console.WriteLine(minRemoval(intervals));
    }
}

JavaScript

function minRemoval(intervals) {
    let cnt = 0;

    // Sort by minimum starting point
    intervals.sort((a, b) => a[0] - b[0]);

    let end = intervals[0][1];
    for (let i = 1; i < intervals.length; i++) {

        // If the current starting point is less than
        // the previous interval's ending point
        // (ie. there is an overlap)
        if (intervals[i][0] < end) {
          
            // Increase cnt and remove the interval
            // with the higher ending point
            cnt++;
            end = Math.min(intervals[i][1], end);
        }

        // Incase of no overlapping, this interval is 
        // not removed and 'end' will be updated
        else
            end = intervals[i][1];
    }

    return cnt;
}

// Driver Code
const intervals = [[1, 2], [2, 3], [3, 4], [1, 3]];
console.log(minRemoval(intervals));

Output

[Approach 2] Sorting by the Ending Values - O(n*log n) Time and O(1) Space

To understand this approach, think of it as trying to keep intervals short so we have more space for other intervals, without overlap. By sorting intervals by their end times, we can easily check if the next interval overlaps with the previous one. If there’s an overlap, we remove the interval with the later end time, so it doesn’t block the next intervals from fitting in. This way, we end up with the minimum number of removals needed to make all intervals non-overlapping.

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// comparator function
bool compare(vector<int>& a, vector<int>& b) {
    return a[1] < b[1];
}

int minRemoval(vector<vector<int> >& intervals) {
	int cnt = 0;
  
    // Sort by minimum ending point
    sort(intervals.begin(), intervals.end(), compare);

    int end = intervals[0][1];

    for (int i = 1; i < intervals.size(); i++) {

        // if there is an overlap increase the count
        if (intervals[i][0] < end)
            cnt++;

        // else increment the ending point
        else
            end = intervals[i][1];
    }

    // return the count
    return cnt;
}

int main() {
    vector<vector<int>> intervals = 
    				{{1, 2}, {2, 3}, {3, 5}, {1, 4}};
    cout << minRemoval(intervals) << endl;
}

Java

import java.util.Arrays;

class GfG {
  
    static int minRemoval(int[][] intervals) {
        int cnt = 0;

        // Sort by minimum ending point
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);

        int end = intervals[0][1];

        for (int i = 1; i < intervals.length; i++) {

            // if there is an overlap increase the count
            if (intervals[i][0] < end)
                cnt++;

            // else increment the ending point
            else
                end = intervals[i][1];
        }

        // return the count
        return cnt;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1, 2}, {2, 3}, {3, 5}, {1, 4}};
        System.out.println(minRemoval(intervals));
    }
}

Python

def minRemoval(intervals):
    cnt = 0

    # Sort by minimum ending point
    intervals.sort(key=lambda x: x[1])

    end = intervals[0][1]

    for i in range(1, len(intervals)):

        # if there is an overlap increase the count
        if intervals[i][0] < end:
            cnt += 1

        # else increment the ending point
        else:
            end = intervals[i][1]

    # return the count
    return cnt

if __name__ == "__main__":
    intervals = [[1, 2], [2, 3], [3, 5], [1, 4]]
    print(minRemoval(intervals))

C#

using System;
using System.Collections.Generic;

class GfG {
  
    // comparator function
    static int minRemoval(int[][] intervals) {
        int cnt = 0;

        // Sort by minimum ending point
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));

        int end = intervals[0][1];

        for (int i = 1; i < intervals.Length; i++) {

            // if there is an overlap increase the count
            if (intervals[i][0] < end)
                cnt++;

            // else increment the ending point
            else
                end = intervals[i][1];
        }

        // return the count
        return cnt;
    }

    static void Main() {
        int[][] intervals = new int[][] {
            new int[] {1, 2}, new int[] {2, 3}, 
            new int[] {3, 5}, new int[] {1, 4}
        };
        Console.WriteLine(minRemoval(intervals));
    }
}

JavaScript

function minRemoval(intervals) {
    let cnt = 0;

    // Sort by minimum ending point
    intervals.sort((a, b) => a[1] - b[1]);

    let end = intervals[0][1];

    for (let i = 1; i < intervals.length; i++) {

        // if there is an overlap increase the count
        if (intervals[i][0] < end)
            cnt++;

        // else increment the ending point
        else
            end = intervals[i][1];
    }

    // return the count
    return cnt;
}

// Driver Code
const intervals = [[1, 2], [2, 3], [3, 5], [1, 4]];
console.log(minRemoval(intervals));

Output

Comment

Article Tags:

Explore

DSA Fundamentals

Data Structures

Algorithms

Advanced

Interview Preparation

Practice Problem