Inserting Intervals: Merging and Maintaining Order

January 10, 2025

Inserting Intervals: Merging and Maintaining Order

Handling intervals is a common task in computational problems, particularly when working with scheduling or range-based queries.

In this article, we’ll address a classic interval problem: inserting a new interval into an existing list of non-overlapping, sorted intervals while ensuring the result is properly merged and remains sorted.

Problem Description

You are given:

A list of non-overlapping intervals, represented as intervals[i] = [start_i, end_i], where start_i and end_i are the start and end times of each interval.
The intervals are sorted in ascending order by their start times.
A new interval, represented as newInterval = [start, end].

Task

Insert newInterval into intervals such that:

The resulting list remains sorted by start times.
Overlapping intervals are merged into a single interval.

Constraints

0≤intervals.length≤1000
$interval.length = 2$ and
0≤start≤end≤1000

Example 1

Input: intervals = [[1,3],[4,6]], newInterval = [2,5]

Output: [[1,6]]

Explanation:
The new interval [2,5] overlaps with both [1,3] and [4,6], so all three are merged into [1,6].

Example 2

Input: intervals = [[1,2],[3,5],[9,10]], newInterval = [6,7]

Output: [[1,2],[3,5],[6,7],[9,10]]

Explanation:
The new interval [6,7] does not overlap with any existing intervals, so it is simply inserted in its correct position.

Approach to Solve the Problem

To solve this problem, we need to carefully handle overlapping intervals and preserve the order of the list. Here’s a step-by-step breakdown:

Step 1: Identify Non-Overlapping Intervals

Before merging, we need to figure out:

Left Intervals: Intervals that end before the new interval starts. These don’t overlap with newInterval and can be added directly to the result.
Right Intervals: Intervals that start after the new interval ends. These also don’t overlap and can be added directly.

Step 2: Merge Overlapping Intervals

If an interval overlaps with the new interval, we merge them by:

Taking the minimum of the start times.
Taking the maximum of the end times.

We continue merging until there are no more overlapping intervals.

Step 3: Combine Results

Once we’ve processed the intervals, combine the left intervals, the merged interval, and the right intervals into a single sorted list.

There are mainly three approach to solve this problem –

Linear Search
Binary Search
Greedy

1. Linear Search

Time complexity: $O (n)$
Space complexity: $O (1)$

Python

C++

Java

JavaScript

Python

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        n = len(intervals)
        i = 0
        res = []

        while i < n and intervals[i][1] < newInterval[0]:
            res.append(intervals[i])
            i += 1

        while i < n and newInterval[1] >= intervals[i][0]:
            newInterval[0] = min(newInterval[0], intervals[i][0])
            newInterval[1] = max(newInterval[1], intervals[i][1])
            i += 1
        res.append(newInterval)

        while i < n:
            res.append(intervals[i])
            i += 1

        return res

C++

class Solution {
public:
    vector> insert(vector>& intervals, vector& newInterval) {
        int n = intervals.size(), i = 0;
        vector> res;

        while (i < n && intervals[i][1] < newInterval[0]) {
            res.push_back(intervals[i]);
            i++;
        }

        while (i < n && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = min(newInterval[0], intervals[i][0]);
            newInterval[1] = max(newInterval[1], intervals[i][1]);
            i++;
        }
        res.push_back(newInterval);

        while (i < n) {
            res.push_back(intervals[i]);
            i++;
        }
        return res;
    }
};

Java

public class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        int n = intervals.length, i = 0;
        List res = new ArrayList<>();

        while (i < n && intervals[i][1] < newInterval[0]) {
            res.add(intervals[i]);
            i++;
        }

        while (i < n && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        res.add(newInterval);

        while (i < n) {
            res.add(intervals[i]);
            i++;
        }

        return res.toArray(new int[res.size()][]);
    }
}

JavaScript

class Solution {
    /**
     * @param {number[][]} intervals
     * @param {number[]} newInterval
     * @return {number[][]}
     */
    insert(intervals, newInterval) {
        let n = intervals.length,
        i = 0,
        res = [];

        while (i < n && intervals[i][1] < newInterval[0]) {
            res.push(intervals[i]);
            i++;
        }

        while (i < n && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        res.push(newInterval);

        while (i < n) {
            res.push(intervals[i]);
            i++;
        }

        return res;
    }
}

2. Binary Search

Time & Space Complexity

Time complexity: O(n)
Space complexity:

Code

C++

Java

Python

JavaScript

C++

class Solution {
public:
    vector> insert(vector>& intervals, vector& newInterval) {
        if (intervals.empty()) {
            return {newInterval};
        }

        int n = intervals.size();
        int target = newInterval[0];
        int left = 0, right = n - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (intervals[mid][0] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        intervals.insert(intervals.begin() + left, newInterval);

        vector> res;
        for (const auto& interval : intervals) {
            if (res.empty() || res.back()[1] < interval[0]) {
                res.push_back(interval);
            } else {
                res.back()[1] = max(res.back()[1], interval[1]);
            }
        }

        return res;
    }
};

Java

public class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        if (intervals.length == 0) {
            return new int[][] { newInterval };
        }

        int n = intervals.length;
        int target = newInterval[0];
        int left = 0, right = n - 1;

        while (left <= right) {
            int mid = (left + right) / 2;
            if (intervals[mid][0] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        List result = new ArrayList<>();
        for (int i = 0; i < left; i++) {
            result.add(intervals[i]);
        }
        result.add(newInterval);
        for (int i = left; i < n; i++) {
            result.add(intervals[i]);
        }

        List merged = new ArrayList<>();
        for (int[] interval : result) {
            if (merged.isEmpty() ||
                merged.get(merged.size() - 1)[1] < interval[0]) {
                merged.add(interval);
            } else {
                merged.get(merged.size() - 1)[1] = Math.max(
                    merged.get(merged.size() - 1)[1],
                    interval[1]
                );
            }
        }

        return merged.toArray(new int[0][]);
    }
}

Python

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        if not intervals:
            return [newInterval]

        n = len(intervals)
        target = newInterval[0]
        left, right = 0, n - 1

        while left <= right:
            mid = (left + right) // 2
            if intervals[mid][0] < target:
                left = mid + 1
            else:
                right = mid - 1

        intervals.insert(left, newInterval)

        res = []
        for interval in intervals:
            if not res or res[-1][1] < interval[0]:
                res.append(interval)
            else:
                res[-1][1] = max(res[-1][1], interval[1])
        return res

JavaScript

class Solution {
    /**
     * @param {number[][]} intervals
     * @param {number[]} newInterval
     * @return {number[][]}
     */
    insert(intervals, newInterval) {
        let n = intervals.length,
        i = 0,
        res = [];

        while (i < n && intervals[i][1] < newInterval[0]) {
            res.push(intervals[i]);
            i++;
        }

        while (i < n && newInterval[1] >= intervals[i][0]) {
            newInterval[0] = Math.min(newInterval[0], intervals[i][0]);
            newInterval[1] = Math.max(newInterval[1], intervals[i][1]);
            i++;
        }
        res.push(newInterval);

        while (i < n) {
            res.push(intervals[i]);
            i++;
        }

        return res;
    }
}

3. Greedy

Time complexity: O(n)
Space complexity:

C++

Java

Python

JavaScript

C++

class Solution {
public:
    vector> insert(vector>& intervals, vector& newInterval) {
        vector> res;
        int newStart = newInterval[0];
        int newEnd = newInterval[1];
        int n = intervals.size();
        for (int i = 0; i < n; i++) {
            if (intervals[i][0] > newEnd) {
                res.push_back(newInterval);
                copy(intervals.begin() + i, intervals.end(), back_inserter(ans));
                return ans;
            } else if (intervals[i][1] < newStart) {
                res.push_back(intervals[i]);
            } else {
                newInterval[0] = min(newInterval[0], intervals[i][0]);
                newInterval[1] = max(newInterval[1], intervals[i][1]);
            }
        }
        res.push_back(newInterval);
        return res;
    }
};

Java

public class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List res = new ArrayList<>();
        for (int[] interval : intervals) {
            if (newInterval == null || interval[1] < newInterval[0]) {
                res.add(interval);
            } else if (interval[0] > newInterval[1]) {
                res.add(newInterval);
                res.add(interval);
                newInterval = null;
            } else {
                newInterval[0] = Math.min(interval[0], newInterval[0]);
                newInterval[1] = Math.max(interval[1], newInterval[1]);
            }
        }
        if (newInterval != null) res.add(newInterval);
        return res.toArray(new int[res.size()][]);
    }
}

Python

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        res = []

        for i in range(len(intervals)):
            if newInterval[1] < intervals[i][0]:
                res.append(newInterval)
                return res + intervals[i:]
            elif newInterval[0] > intervals[i][1]:
                res.append(intervals[i])
            else:
                newInterval = [
                    min(newInterval[0], intervals[i][0]),
                    max(newInterval[1], intervals[i][1]),
                ]
        res.append(newInterval)
        return res

JavaScript

class Solution {
    /**
     * @param {number[][]} intervals
     * @param {number[]} newInterval
     * @return {number[][]}
     */
    insert(intervals, newInterval) {
        const res = [];
        for (const interval of intervals) {
            if (newInterval === null || interval[1] < newInterval[0]) {
                res.push(interval);
            } else if (interval[0] > newInterval[1]) {
                res.push(newInterval);
                res.push(interval);
                newInterval = null;
            } else {
                newInterval[0] = Math.min(interval[0], newInterval[0]);
                newInterval[1] = Math.max(interval[1], newInterval[1]);
            }
        }
        if (newInterval !== null) res.push(newInterval);
        return res;
    }
}

Unlock this article for Free,
by logging in

Inserting Intervals: Merging and Maintaining Order