LeetCode 57 – Insert Interval Problem with Java, C++, and Python Solutions

LeetCode 57 – Insert Interval: Given a sorted list of non‑overlapping intervals and a new interval, insert the new interval and merge any overlapping intervals so that the final list remains sorted and non‑overlapping.

Example 1: intervals = [[1,3],[6,9]], newInterval = [2,5] → [[1,5],[6,9]]

Example 2: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] → [[1,2],[3,10],[12,16]] (the new interval overlaps three existing intervals).

Constraints: 0 ≤ intervals.length ≤ 10⁴; each interval has two integers 0 ≤ start ≤ end ≤ 10⁵; intervals are sorted by start.

Analysis: An interval does not overlap if its end is less than the start of the new interval, or its start is greater than the end of the new interval. Non‑overlapping intervals are copied directly; overlapping intervals are merged by taking the minimum start and maximum end.

Java solution:

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

C++ solution:

vector
> insert(vector
>& intervals, vector
& newInterval) {
    vector
> res;
    bool finish = false;
    for (auto const &interval : intervals) {
        if (finish || interval[1] < newInterval[0]) {
            res.emplace_back(interval);
        } else if (interval[0] > newInterval[1]) {
            res.emplace_back(newInterval);
            res.emplace_back(interval);
            finish = true;
        } else {
            newInterval[0] = min(newInterval[0], interval[0]);
            newInterval[1] = max(newInterval[1], interval[1]);
        }
    }
    if (!finish) res.emplace_back(newInterval);
    return res;
}

Python solution:

def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
    ans = []
    for interval in intervals:
        if not newInterval or interval[1] < newInterval[0]:
            ans.append(interval)
        elif interval[0] > newInterval[1]:
            ans.append(newInterval[:])
            ans.append(interval)
            newInterval.clear()
        else:
            newInterval[0] = min(newInterval[0], interval[0])
            newInterval[1] = max(newInterval[1], interval[1])
    if newInterval:
        ans.append(newInterval)
    return ans