Question
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:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
Stats
| Frequency | 5 |
| Difficulty | 4 |
| Adjusted Difficulty | 4 |
| Time to use | -------- |
Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)
Solution
This is not an easy question, though it’s similar to the question “Merge Intervals”.
First code is my solution.
Second code is from this repo. This is only 1 iteration, but in 3 stages. First, add all intervals ahead of newInterval into ans. Second, merge anything that can be merged with newInterval, and add to ans. Third, add the rest of intervals into ans.
Third code is from this blog. It’s a very tricky solution.
My code
My code
/**
* Definition for an interval.
* public class Interval {
* int start;
* int end;
* Interval() { start = 0; end = 0; }
* Interval(int s, int e) { start = s; end = e; }
* }
*/
public class Solution {
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
if (intervals == null) {
return null;
}
int p = 0;
while (p < intervals.size() && intervals.get(p).start < newInterval.start) {
p++;
}
intervals.add(p, newInterval);
if (p > 0) {
p--;
}
// start merging from (p)th element
while (p < intervals.size() - 1) {
if (intervals.get(p).end >= intervals.get(p + 1).start) {
intervals.get(p).end = Math.max(intervals.get(p).end, intervals.get(p + 1).end);
intervals.remove(p + 1);
} else {
p++;
}
}
return intervals;
}
}
Second code.
public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
ArrayList<Interval> re = new ArrayList<Interval>();
int len = intervals.size();
int i = 0;
while (i < len) {
Interval temp = intervals.get(i);
if (temp.end < newInterval.start)
re.add(temp);
else if (temp.start > newInterval.end)
break;
else {
newInterval.start = Math.min(temp.start, newInterval.start);
newInterval.end = Math.max(temp.end, newInterval.end);
}
i++;
}
re.add(newInterval);
while (i < len) {
re.add(intervals.get(i));
i++;
}
return re;
}
Third code, a popular solution. Very tricky and concise.
public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
ArrayList<Interval> result = new ArrayList<Interval>();
for(Interval interval: intervals){
if(interval.end < newInterval.start){
result.add(interval);
}else if(interval.start > newInterval.end){
result.add(newInterval);
newInterval = interval;
}else if(interval.end >= newInterval.start
|| interval.start <= newInterval.end){
newInterval = new Interval(
Math.min(interval.start, newInterval.start),
Math.max(newInterval.end, interval.end));
}
}
result.add(newInterval);
return result;
}