Merge Intervals trick, break intervals to pairs

wei zhang
wei zhang
Aug 23, 2017 · 2 min read

Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?

Let see one test example:

[
[1,10],
[2,3],
[5,8],
[4,7]
]

One useful trick for dealing with this kind of intervals merging is break the intervals to pairs, one intervals to two pairs, start paired with 1 which end paired with -1,

vector<pair<int, int>> break_intervals(vector<Interval> &airplanes) {
vector<pair<int, int>> dp;


for(auto i : airplanes) {
pair<int, int> tmp1, tmp2;
tmp1.first = i.start;
tmp1.second = 1;
dp.push_back(tmp1);
tmp2.first = i.end;
tmp2.second = -1;
dp.push_back(tmp2);
}

return(dp);
}
1 1
10 -1
2 1
3 -1
5 1
8 -1
4 1
7 -1

Then we sort the pairs by time, we have

1 1
2 1
3 -1
4 1
5 1
7 -1
8 -1
10 -1

The max is the max of the prefix sum for the second component.

int countOfAirplanes(vector<Interval> &airplanes) {
// write your code here

int res = 0, cur_cnt = 0;
vector<pair<int, int>> dp;
dp = break_intervals(airplanes);


std::sort(dp.begin(), dp.end(), Solution::cmp)

for (auto i : dp) {
cur_cnt += i.second;
res = max(res, cur_cnt);
}


return(res);

}

static bool cmp(const pair<int, int> &l, const pair<int, int> &r) {
if (l.first != r.first) {
return(l.first < r.first);
}

return(l.second < r.second);
}

Merge Intervals

Given a collection of intervals, merge all overlapping intervals.

Have you met this question in a real interview?

Example

Given intervals => merged intervals:

[                     [
[1, 3], [1, 6],
[2, 6], => [8, 10],
[8, 10], [15, 18]
[15, 18] ]
]

Using the same trick, we have the following procedure to outputting result:

vector<Interval> merge(vector<Interval> &intervals) {

int cur_cnt = 0, tmp_left;
vector<pair<int, int>> dp;
vector<Interval> res;
dp = break_intervals(intervals);

std::sort(dp.begin(), dp.end(), Solution::cmp);
for (auto i : dp) {
if(cur_cnt == 0) {
tmp_left = i.first;
}

cur_cnt += i.second;

if(cur_cnt == 0) {
Interval tmp(tmp_left, i.first);
res.push_back(tmp);
}
}
return(res);
}

Stay tunned, building outline problem is coming

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade