Formatted question description: https://leetcode.ca/all/57.html

57. Insert Interval

Difficulty: Hard.
Related Topics: Array, Sort.
Similar Questions: Merge Intervals, Range Module.

Problem

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

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

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
Output: [[1,2],[3,10],[12,16]]
Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

Algorithm

This problem asks us to insert a new interval into a series of non-overlapping intervals, possibly merging with existing intervals. We can iterate through the given interval set one by one and compare. There are two possible situations: overlapping or non-overlapping. Non-overlapping cases are straightforward, we can simply insert the new interval at the corresponding position. Overlapping cases are more complex, sometimes there may be multiple overlaps, so we need to update the range of the new interval to include all overlaps, and then add the new interval to the result res, finally adding the remaining intervals after the new interval to the result res.

The specific approach is to use a variable cur to iterate through the intervals. If the end position of the current cur interval is less than the start position of the interval to be inserted, there is no overlap, so add the cur interval to the result res and then increment cur by 1. Continue this until cur is out of bounds or there is an overlap, then exit the while loop. Then, use another while loop to handle all overlapping intervals, each time updating the new interval by taking the minimum of the starting positions and the maximum of the ending positions of two intervals, then increment cur by 1. Continue this until cur is out of bounds or there is no overlap, then exit the while loop. After that, add the updated new interval to the result res, and add the intervals after cur to the result res.

Code

import java.util.ArrayList;
import java.util.List;

public class Insert_Interval {


	public class Solution_no_boolean_flag {

	    List<Interval> list = new ArrayList<Interval>();

	    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {

	        if (intervals == null || newInterval == null) {
	            return list;
        	}
	        if (intervals.size() == 0) {
	            list.add(newInterval);
	            return list;
	        }

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

	            Interval current = intervals.get(i);

	            if (current.end < newInterval.start) {
	                list.add(current);
	            }

	            else if (newInterval.end < current.start) {
	                list.add(newInterval);
	                newInterval = current; // @note: update newInterval as the pending to be put in list
	            }

	            else /* overlap: if (current.end >= newInterval.start) */ {
	                Interval combine =
                        new Interval(
                            Math.min(current.start, newInterval.start),
                            Math.max(current.end, newInterval.end)
                        );
	                // list.add(combine);
	                newInterval = combine;
	            }
	        }

	        // @note: last one! check lastone is merged
	        // [[1,5]], [6,8]
	        // [[1,5]], [2,3]
	        // Interval lastsecond = list.get(list.size() - 1);
	        // if (lastone.start > lastsecond.end) {
	        //     list.add(lastone);
	        // }

	        list.add(newInterval);

	        return list;
	    }
	}

}

############

class Solution {
    public int[][] insert(int[][] intervals, int[] newInterval) {
        List<int[]> list = new LinkedList<>();
        int i = 0;
        while ((i < intervals.length) && (intervals[i][1] < newInterval[0]))
            list.add(intervals[i++]);
        while ((i < intervals.length) && (intervals[i][0] <= newInterval[1])) {
            newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
            i++;
        }
        list.add(newInterval);
        while (i < intervals.length) list.add(intervals[i++]);
        return list.toArray(new int[list.size()][]);
    }
}

// OJ: https://leetcode.com/problems/insert-interval/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        int s = newInterval[0], e = newInterval[1];
        vector<vector<int>> ans;
        for (auto &intv : intervals) {
            if (s > e) ans.push_back(intv);
            else if (intv[0] > e) {
                ans.push_back({ s, e });
                s = e + 1;
                ans.push_back(intv);
            } else if (intv[1] < s) ans.push_back(intv);
            else {
                s = min(s, intv[0]);
                e = max(e, intv[1]);
            }
        }
        if (s <= e) ans.push_back({ s, e });
        return ans;
    }
};

# python3

'''
>>> a = [1,2,3,4,5]
>>> a[1]
2
>>> a[~1]
4
'''
class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        start = newInterval[0]
        end = newInterval[1]

        left = list(filter(lambda x: x[1] < start, intervals)) # cast via list()
        right = list(filter(lambda x: x[0] > end, intervals))

        if left + right != intervals:
            start = min(start, intervals[len(left)][0]) # note, left not -1, because index starts at 0
            end = max(end, intervals[~len(right)][1]) # same, starting at right with index=0

        return left + [[start, end]] + right


class Solution: # re-use Leetcode-56's merge solution
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
        intervals.append(newInterval)
        return self.merge(intervals)

    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        ans = []
        for intv in sorted(intervals, key=lambda x: x[0]):
            if ans and ans[-1][1] >= intv[0]:
                ans[-1][1] = max(ans[-1][1], intv[1])
            else:
                ans.append(intv)
        return ans

func insert(intervals [][]int, newInterval []int) [][]int {
	intervals = append(intervals, newInterval)
	return merge(intervals)
}

func merge(intervals [][]int) [][]int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	st, ed := intervals[0][0], intervals[0][1]
	var ans [][]int
	for _, e := range intervals[1:] {
		if ed < e[0] {
			ans = append(ans, []int{st, ed})
			st, ed = e[0], e[1]
		} else if ed < e[1] {
			ed = e[1]
		}
	}
	ans = append(ans, []int{st, ed})
	return ans
}

using System;
using System.Collections.Generic;

public class Solution {
    public int[][] Insert(int[][] intervals, int[] newInterval) {
        var result = new List<int[]>();
        var i = 0;

        while (i < intervals.Length && intervals[i][1] < newInterval[0])
        {
            result.Add(intervals[i++]);
        }

        while (i < intervals.Length && intervals[i][0] <= newInterval[1] && intervals[i][1] >= newInterval[0])
        {
            newInterval[0] = Math.Min(intervals[i][0], newInterval[0]);
            newInterval[1] = Math.Max(intervals[i][1], newInterval[1]);
            ++i;
        }
        result.Add(newInterval);

        while (i < intervals.Length)
        {
            result.Add(intervals[i++]);
        }

        return result.ToArray();
    }
}

function insert(intervals: number[][], newInterval: number[]): number[][] {
    let [st, ed] = newInterval;
    const ans: number[][] = [];
    let insert = false;
    for (const [s, e] of intervals) {
        if (ed < s) {
            if (!insert) {
                ans.push([st, ed]);
                insert = true;
            }
            ans.push([s, e]);
        } else if (e < st) {
            ans.push([s, e]);
        } else {
            st = Math.min(st, s);
            ed = Math.max(ed, e);
        }
    }
    if (!insert) {
        ans.push([st, ed]);
    }
    return ans;
}

impl Solution {
    pub fn insert(intervals: Vec<Vec<i32>>, new_interval: Vec<i32>) -> Vec<Vec<i32>> {
        let mut inserted = false;
        let mut result = vec![];

        let (mut start, mut end) = (new_interval[0], new_interval[1]);
        for iter in intervals.iter() {
            let (cur_st, cur_ed) = (iter[0], iter[1]);
            if cur_ed < start {
                result.push(vec![cur_st, cur_ed]);
            } else if cur_st > end {
                if !inserted {
                    inserted = true;
                    result.push(vec![start, end]);
                }
                result.push(vec![cur_st, cur_ed]);
            } else {
                start = std::cmp::min(start, cur_st);
                end = std::cmp::max(end, cur_ed);
            }
        }

        if !inserted {
            result.push(vec![start, end]);
        }
        result
    }
}

57 - Insert Interval

57. Insert Interval

Problem

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

57. Insert Interval

Problem

Algorithm

Code

All Problems

All Solutions