Merge Intervals trick, break intervals to pairs
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 -1The 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
