LeetCode: Merge Intervals

By | 2012 年 10 月 5 日

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

Analyze

This is a simple question, just sort the intervals by start first then check them one by one and merge adjacent intervals if necessary.

Notes

  • vector::back(),返回的是最后一个元素的引用
  • sort(vec.begin(),vec.end(),customLessThan),customLessThan的原型
  • vector::push_back(anItem),会调用anItem的拷贝构造函数,将拷贝所得新的元素放入vector
  • class的static数据成员,只能在类定义中声明;初始化需要在类定义之外用type className::aMember = initiaValue来进行

Solutions:

Ruby

# Definition for an interval.
# class Interval
#     attr_accessor :start, :end
#     def initialize(s=0, e=0)
#         @start = s
#         @end = e
#     end
# end

def clone(interval)
    Interval.new(interval.start, interval.end)
end

# @param {Interval[]} intervals
# @return {Interval[]}
def merge(intervals)
    intervals.sort!{|inv1, inv2| inv1.start <=> inv2.start}
    result = []
    return result if intervals.empty?

    opening = clone(intervals.first)
    intervals[1..-1].each do |inv|
        if opening.end >= inv.start
            opening.end = inv.end if opening.end < inv.end
        else
            result << opening
            opening = clone(inv)
        end
    end
    result << opening

    result
end

C++, 4ms过小集合,但是不知道为什么大集合运行时错误

/**
 * 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 isEarlierThan(const Interval &int1, const Interval &int2){
    return int1.start <= int2.start;
}
class Solution {
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        sort(intervals.begin(),intervals.end(),isEarlierThan);
        Interval *openInt = NULL;
        vector<Interval> result;
        for(int i = 0 ; i < intervals.size(); ++i) {
            Interval &curInt = intervals[i];
            if(openInt == NULL || openInt->end < curInt.start){
                result.push_back(curInt);
                openInt = &(result.back());
            }else if(curInt.end > openInt->end) {
                openInt->end = curInt.end;
            }
        }
        return result;
    }
};

C++, Code rewrite at 2012-12-24, 60ms pass large set

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
class Solution {
    static bool earlier(const Interval &int0, const Interval &int1) {
        return int0.start < int1.start;
    }
public:
    vector<Interval> merge(vector<Interval> &intervals) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(intervals.size() <= 1) return intervals;
        sort(intervals.begin(),intervals.end(),Solution::earlier);
        vector<Interval> ret;
        Interval openInt = intervals[0];
        for(int i = 0; i < intervals.size(); ++i) {
            Interval &cur = intervals[i];
            if(openInt.end < cur.start) {
                ret.push_back(openInt);
                openInt = cur;
            } else {
                if (openInt.end < cur.end) openInt.end = cur.end;
            }
        }
        ret.push_back(openInt);
        return ret;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注