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].
============
in-place one:
vector<Interval> adjustEnd(vector<Interval>& intervals, int i, Interval newInterval) {
int j = i + 1;
while (j <= intervals.size()) {
if (j == intervals.size()) {
intervals[i].end = max(newInterval.end, intervals[i].end);
return intervals;
}
if (newInterval.end < intervals[j].start) {
intervals[i].end = max(newInterval.end, intervals[i].end);
return intervals;
} else if (newInterval.end >= intervals[j].start &&
newInterval.end <= intervals[j].end) {
intervals[i].end = intervals[j].end;
intervals.erase(intervals.begin() + j);
return intervals;
} else {
intervals.erase(intervals.begin() + j);
}
}
return intervals;
}
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
if (intervals.size() == 0) {
intervals.push_back(newInterval);
return intervals;
}
int size = intervals.size();
if (newInterval.start > intervals[size - 1].end) {
intervals.push_back(newInterval);
return intervals;
}
int i = 0;
while (i < intervals.size()) {
if (newInterval.start >= intervals[i].start &&
newInterval.start <= intervals[i].end) {
return adjustEnd(intervals, i, newInterval);
} else if (newInterval.start < intervals[i].start) {
if (newInterval.end < intervals[i].start) {
intervals.insert(intervals.begin() + i, newInterval);
return intervals;
} else if (newInterval.end >= intervals[i].start) {
intervals[i].start = newInterval.start;
return adjustEnd(intervals, i, newInterval);
}
}
i++;
}
return intervals;
}
=============
Short and elegant below in java:
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
if(newInterval == null) return intervals;
int first = 0;
while(first < intervals.size() && newInterval.start > intervals.get(first).end)
first++;
while(first < intervals.size() && newInterval.end >= intervals.get(first).start)
{
newInterval = new Interval(Math.min(newInterval.start,intervals.get(first).start),
Math.max(newInterval.end,intervals.get(first).end));
intervals.remove(first);
}
intervals.add(first,newInterval);
return intervals;
}
=============== Recent one ========
class Solution {
public:
bool overlap(vector<int> interval, int& first, int& second) {
if ((first >= interval[0] && first <= interval[1]) ||
(second >= interval[0] && second <= interval[1])) {
first = min(interval[0], first);
second = max(interval[1], second);
return true;
}
return false;
}
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> sol;
int first = newInterval[0];
int second = newInterval[1];
if (intervals.size() == 0) {
sol.push_back(vector<int> {first, second});
return sol;
}
int i = 0;
bool merged = false;
for (i = 0; i < intervals.size(); i++) {
bool is_overlap = overlap(intervals[i], first, second);
if (!is_overlap) {
if (second < intervals[i][0]) {
if (!merged) {
sol.push_back(vector<int> {first, second});
merged = true;
}
sol.push_back(intervals[i]);
} else if (intervals[i][1] < first) {
sol.push_back(intervals[i]);
}
}
}
if (!merged) {
sol.push_back(vector<int> {first, second});
}
return sol;
}
};
=========== Another one =======
class Solution {
public:
int overlap(vector<int>& newInterval, vector<int>& interval) {
if (newInterval[1] < interval[0]) {
// newInterval < interval
return -1;
} else if (newInterval[0] > interval[1]) {
// newInterval > interval
return 1;
} else {
// Merge.
return 0;
}
}
vector<vector<int>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
vector<vector<int>> sol;
if (intervals.size() == 0) {
sol.push_back(newInterval);
return sol;
}
int iter = 0;
while (iter < intervals.size()) {
int option = overlap(newInterval, intervals[iter]);
if (option == 0) {
// Merge going-on
newInterval[0] = min(newInterval[0], intervals[iter][0]);
newInterval[1] = max(newInterval[1], intervals[iter][1]);
} else if (option == -1) {
// merge completed.
sol.push_back(newInterval);
while (iter < intervals.size()) {
sol.push_back(intervals[iter]);
iter++;
}
return sol;
} else {
// Merge ahead
sol.push_back(intervals[iter]);
}
iter++;
}
sol.push_back(newInterval);
return sol;
}
};
