Programming Interview Question - Merge Intervals

This post will explore the solutions to the question #4 of the famous website cakeinreview (here the link).

Programming Interview Question - Merge Intervals - Problem Statement

Given a list of pair of integers return a list of merged or condensed intervals.

Given for instance the following input list

your solution should return:

Your function should take care of corner cases like merging two intervals like the following $(0,1),(1,2)$ in $(0,2)$. Give a $O(n^2)$ solution first. Then try to solve it in $O(nlog(n))$.

Merge Intervals Problem - Solution 1; $O(n^2)$
What properties two interval have to have in order to be merged together into one? In order $(a,b)$ and $(c,d)$  to be merged together the following has to hold:

$(a \leq c \; \wedge \; b \geq c ) \; \wedge \; (a \geq c \; \wedge \; a \leq d )$

which basically tests if $(a,b)$ is partially or completely contained into $(c,d)$.
Given that, it is easy to write a quadratic function. We start with an empty list of merged intervals. Then for each interval from the input we check whether we can merge it with one of the already merged intervals. If we can, we simply update the interval otherwise, we insert that interval in the list of merged ones.

Now the question is, when we agreed on the fact that $(a,b)$ and $(c,d)$ can be merged, how this is gonna happen? We take the minimum from the left parts of the intervals and the maximum from the right parts i.e.$merge (a,b),(c,d) = (min(a,c),max(b,d))$.

The complexity of this approach is quadratic because the worst case is when no intervals will be merged and we end up with a number of iteration equals to $1+2+3+4 +\ldots +n$.

Best case is $O(n)$ is when all the intervals can be merged into one.

Here the code for the quadratic version


auto canupdate = [](const pair<int, int> p, const pair<int,int> p1){
return
(p.first <= p1.first && p.second >= p1.first) ||
(p.first>= p1.first && p.first <= p1.second);

};
//complexity is quadratic we can do better (nlgn)
vector<pair<int,int>> mergeSlots(vector<pair<int, int>> slots){
vector<pair<int,int>> cond;

for( auto p : slots){
bool update = false;

for(int i=0 ; i < cond.size(); ++i){
if(canupdate(p,cond[i])){
cond[i].first = min(cond[i].first,p.first);
cond[i].second = max(cond[i].second,p.second);
update = true;
}

}

if(!update)
cond.push_back(p);

}
return cond;
}



Merge Intervals Problem - Solution 2; $O(nlog(n))$
What if we sort the intervals by the left part first?
This will sort the list such that mergeable intervals will be one after the other. We start inserting the first element in the final list, and then for all the other intervals we simply check whether it can be mergeable with the head of the result list. If not we insert the interval in the result and keep going until all the input intervals are examined. The complexity of this phase is linear but the overall complexity of this approach is dominated by the sorting phase.

This allows us to write the following $O(nlog(n))$ solution.


auto canupdate = [](const pair<int, int> p, const pair<int,int> p1){
return
(p.first <= p1.first && p.second >= p1.first) ||
(p.first>= p1.first && p.first <= p1.second);

};

vector<pair<int,int>> mergeSlots2(vector<pair<int, int>> slots){
vector<pair<int,int>> cond;

std::sort(slots.begin() , slots.end() ,
[](const auto& p, const auto& p1)
{return p.first < p1.first || (p.first <= p1.first && p.second < p1.second);});

int i=1;
cond.push_back(slots[0]);
for( ; i < slots.size() ; i++){
auto p = slots[i];
bool update = false;

if(canupdate(p,cond.back())){
cond.back().first = min(cond.back().first,p.first);
cond.back().second = max(cond.back().second,p.second);
update = true;
}

if(!update)
cond.push_back(p);

}
return cond;
}



Be the first to leave a comment. Don’t be shy.