Welcome to Subscribe On Youtube
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 } }