e******i
发帖数: 106 | 1 merge interval 这道题一开始最好需要对各个interval进行排序么 |
p*****2
发帖数: 21240 | 2
不需要吧。
【在 e******i 的大作中提到】
: merge interval 这道题一开始最好需要对各个interval进行排序么
|
e******i
发帖数: 106 | 3
只是感觉如果先sort下，然后只需要根据end来判断会简单点
【在 p*****2 的大作中提到】
:
: 不需要吧。
|
j*****y
发帖数: 1071 | 4 我也觉得先 sort会比叫简单点，如果不 sort的话， 在合并的过程中也需要通过
sort来确定那些 合并后的 non-overlapping的 interval 的位置。
【在 e******i 的大作中提到】
:
: 只是感觉如果先sort下，然后只需要根据end来判断会简单点
|
w****g
发帖数: 3 | 5 我用的是先sort的解法。
http://www.yangsheep.net/wuyang/wordpress/?p=727
class Solution {
public:
struct mycmpclass {
bool operator() (Interval i,Interval j) { return (i.start < j.start); }
} mycmpobject;
vector merge(vector &intervals) {
vector ans;
if(intervals.empty()) return ans;
sort(intervals.begin(), intervals.end(), mycmpobject);
Interval cur=intervals[0];
for(int i = 1; i < intervals.size(); i++) {
if(cur.end >= intervals[i].start) cur.end = max(cur.end, intervals[i].
end);
else {
ans.push_back(cur);
cur = intervals[i];
}
}
ans.push_back(cur);
return ans;
}
}; |
e******i
发帖数: 106 | 6 merge interval 这道题一开始最好需要对各个interval进行排序么 |
p*****2
发帖数: 21240 | 7
不需要吧。
【在 e******i 的大作中提到】
: merge interval 这道题一开始最好需要对各个interval进行排序么
|
e******i
发帖数: 106 | 8
只是感觉如果先sort下，然后只需要根据end来判断会简单点
【在 p*****2 的大作中提到】
:
: 不需要吧。
|
j*****y
发帖数: 1071 | 9 我也觉得先 sort会比叫简单点，如果不 sort的话， 在合并的过程中也需要通过
sort来确定那些 合并后的 non-overlapping的 interval 的位置。
【在 e******i 的大作中提到】
:
: 只是感觉如果先sort下，然后只需要根据end来判断会简单点
|
w****g
发帖数: 3 | 10 我用的是先sort的解法。
http://www.yangsheep.net/wuyang/wordpress/?p=727
class Solution {
public:
struct mycmpclass {
bool operator() (Interval i,Interval j) { return (i.start < j.start); }
} mycmpobject;
vector merge(vector &intervals) {
vector ans;
if(intervals.empty()) return ans;
sort(intervals.begin(), intervals.end(), mycmpobject);
Interval cur=intervals[0];
for(int i = 1; i < intervals.size(); i++) {
if(cur.end >= intervals[i].start) cur.end = max(cur.end, intervals[i].
end);
else {
ans.push_back(cur);
cur = intervals[i];
}
}
ans.push_back(cur);
return ans;
}
}; |
j*****y
发帖数: 1071 | 11 二爷能讲讲你不 sort 的话是如何 merge的吗 ? thanks.
不需要吧。
【在 e******i 的大作中提到】
: merge interval 这道题一开始最好需要对各个interval进行排序么
|
f*******t
发帖数: 7549 | |
