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

57. Insert Interval

Level

Hard

Description

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

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

Code

Java

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;
	    }
	}

}

All Problems

All Solutions