A 'insert first deal with overlapping later solution'

• Really a lazy try, didn't even use binary search to find insert location, surprised it's accepted. But it's pretty easy to understand.
Basic concept is to insert new interval at index i first, then deal with the potential overlapping with i - 1 and i + 1 if applicable.

``````class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
vector<Interval> returnValue(intervals);
if (intervals.empty())
{
returnValue.push_back(newInterval);
return returnValue;
}
int insertLocation(-1);
for(int i = 0; i < intervals.size(); ++ i)
{
if (intervals[i].start >= newInterval.start)
{
insertLocation = i;
returnValue.insert(returnValue.begin() + i, newInterval);
break;
}
}
if (insertLocation == -1)
{
returnValue.push_back(newInterval);
insertLocation = returnValue.size() - 1;
}
// Handle overlapping
handleOverlapping(returnValue, insertLocation);

return returnValue;
}

void handleOverlapping(vector<Interval> & intervals, int index)
{
// check previous first
if (index - 1 >= 0)
{
if (intervals[index - 1].end >= intervals[index].start)
{
intervals[index - 1].end = max(intervals[index].end, intervals[index - 1].end);
intervals.erase(intervals.begin() + index, intervals.begin() + index + 1);
handleOverlapping(intervals, index -1);
}
}
if (index + 1 < intervals.size())
{
if (intervals[index + 1].start <= intervals[index].end)
{
if (intervals[index  + 1].end >= intervals[index].end)
{
intervals[index].end = intervals[index + 1].end;
}
intervals.erase(intervals.begin() + index + 1, intervals.begin() + index + 2);
handleOverlapping(intervals, index);
}
}
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.