Formatted question description:

57. Insert Interval




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].


There are two situations, overlapping or non-overlapping.

The non-overlapping situation is best. Just insert the new interval directly into the corresponding position.

The overlapping situation is more complicated. Sometimes there will be multiple overlaps, and the new interval needs to be updated. Range so as to include all overlaps, then add the new interval to the result res, and finally add the latter interval to the result res. The specific idea is to use a variable cur to traverse the interval.

  • If the end position of the current cur interval is less than the start position of the interval to be inserted, it means that there is no overlap, then the cur interval is added to the result res, and then cur increments by 1.
  • Until cur goes out of bounds or overlaps the while loop exits, and then uses a while loop to process all overlapping intervals, each time the smaller value of the start position of the two intervals and the larger value of the end position are used to update the insert Interval, then cur increments by 1.

The while loop exits until cur is out of bounds or there is no overlap. Then add the updated new interval to the result res, and then add the interval after cur to the result



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) {
	            return list;

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

	            Interval current = intervals.get(i);

	            if (current.end < newInterval.start) {

	            else if (newInterval.end < current.start) {
	                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);
	        // }


	        return list;


All Problems

All Solutions