Created
October 29, 2013 15:09
-
-
Save zsh-89/7216466 to your computer and use it in GitHub Desktop.
Leetcode: Merge Intervals
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Solution { | |
public: | |
struct InCmp { | |
bool operator()(const Interval & x, const Interval & y) const { | |
return x.start < y.start; | |
} | |
}; | |
vector<Interval> merge(vector<Interval> &v) { | |
if (v.size() == 0) return v; | |
InCmp cmp; | |
sort(v.begin(), v.end(), cmp); | |
int emax = v[0].end; Interval intv = v[0]; | |
vector<Interval> ans; | |
for (int i = 1; i < v.size(); ++i) { | |
if (v[i].start > emax) { | |
ans.push_back(intv); | |
intv = v[i]; | |
emax = v[i].end; | |
} | |
else { | |
emax = max(emax, v[i].end); | |
intv.end = emax; | |
} | |
} | |
ans.push_back(intv); | |
return ans; | |
} | |
}; |
sort一遍维护rightmax(区间右值)是核心.
不错的做法,我的方法是比较Naive的方法,看起来没那么美观
sort一遍维护rightmax(区间右值)是核心.
不错的做法,我的方法是比较Naive的方法,看起来没那么美观
其实思路是一样的, 就是你的循环不需要两层, 而我不需要endmax变量, 它已经隐含在{当前区间}中了.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
这道题应该曾经是大股沟的面试题的
sort一遍维护rightmax(区间右值)是核心.