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小值吧
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "url": "http://www.acmerblog.com/leetcode-merge-intervals-5514.html", "fetch_time": 1503544238000000000, "content_mime_type": "text/html", "warc_filename": "crawl-data/CC-MAIN-2017-34/segments/1502886126027.91/warc/CC-MAIN-20170824024147-20170824044147-00212.warc.gz", "warc_record_offset": 470119073, "warc_record_length": 12619, "token_count": 458, "char_count": 1323, "score": 3.578125, "int_score": 4, "crawl": "CC-MAIN-2017-34", "snapshot_type": "longest", "language": "en", "language_score": 0.19558016955852509, "file_path": "/sailhome/yjruan/project/latent-lm/data/processed/finemath-4plus/finemath-4plus/train-00050-of-00064.parquet"}