首页 > ACM题库 > LeetCode > LeetCode-Merge Intervals[区间合并]
2014
04-02

LeetCode-Merge Intervals[区间合并]

题目难度:4  面试频率:5

描述:

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].

链接:http://oj.leetcode.com/problems/merge-intervals/

刚开始在想是不是要用区间树或线段树之类。但是区间树也只是能查找到一个有重叠的区间,不适合本题。实际上,按照贪心算法就行了,先按区间的开始位置排序,再遍历一边,查看是否需要合并。时间复杂度O(nlogn).

/**
 * 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小值吧