2014
04-02

# LeetCode-Merge Intervals[区间合并]

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

/**
* Definition for an interval.
* struct Interval {
*     int start;
*     int end;
*     Interval() : start(0), end(0) {}
*     Interval(int s, int e) : start(s), end(e) {}
* };
*/
bool Comp(const Interval &a, const Interval &b){
return a.start<b.start;
};
class Solution {
public:
vector<Interval> merge(vector<Interval> &intervals) {
// IMPORTANT: Please reset any member data you declared, as
// the same Solution instance will be reused for each test case.
vector<Interval> re;
if(intervals.size()==0) return re;
sort(intervals.begin(),intervals.end(),Comp);
Interval tmp=*(intervals.begin());
vector<Interval>::iterator i;
for(i=intervals.begin(),i++;i!=intervals.end();i++){
if(tmp.end>=i->start){
tmp.end=max(tmp.end,i->end);
}
else{
re.push_back(tmp);
tmp=*i;
}
}
re.push_back(tmp);
return re;
}
};

1. 第一题是不是可以这样想，生了n孩子的家庭等价于n个家庭各生了一个1个孩子，这样最后男女的比例还是1:1

2. #!/usr/bin/env python
def cou(n):
arr =
i = 1
while(i<n):
arr.append(arr[i-1]+selfcount(i))
i+=1
return arr[n-1]

def selfcount(n):
count = 0
while(n):
if n%10 == 1:
count += 1
n /= 10
return count

3. 换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将其抛弃。
应该是，不可能小于合并后的第K小值吧