[Leetcode][Python]56: Merge Intervals

# -*- coding: utf8 -*-
'''
__author__ = 'dabay.wang@gmail.com' 56: Merge Intervals
https://oj.leetcode.com/problems/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]. ===Comments by Dabay===
这道题想起来比较简单,实现的时候恼火。
技巧在与,不是一个个地插入到已有的序列,而是把已有的序列插入到一个标杆Interval前面、交叉、后面。 对于每一个序列中的Interval,
- 如果它的end比标杆的start小,插入到前面
- 如果它的start比标杆的end大,插入到后面
- 如果它和标杆有交集,更新标杆的start和end
'''
# Definition for an interval.
class Interval:
def __init__(self, s=0, e=0):
self.start = s
self.end = e class Solution:
# @param intervals, a list of Interval
# @return a list of Interval
def merge(self, intervals):
def insert(interval, merged):
new_merged = []
i = 0
s = interval.start
e = interval.end
while i < len(merged):
if merged[i].end < s:
new_merged.append(merged[i])
i = i + 1
continue
if e < merged[i].start:
new_merged = new_merged + [Interval(s, e)] + merged[i:]
break
s = min(s, merged[i].start)
e = max(e, merged[i].end)
i = i + 1
else:
new_merged.append(Interval(s, e))
return new_merged if len(intervals) <= 1:
return intervals merged = [intervals[0]]
i = 1
while i < len(intervals):
merged = insert(intervals[i], merged)
i = i + 1 return merged def main():
sol = Solution()
i1 = Interval(2,3)
i2 = Interval(4,5)
i3 = Interval(2,2)
i4 = Interval(15,18)
intervals = [i1,i2,i3,i4]
intervals = sol.merge(intervals)
for interval in intervals:
print "[%s, %s] " % (interval.start, interval.end),
print if __name__ == "__main__":
import time
start = time.clock()
main()
print "%s sec" % (time.clock() - start)
上一篇:LeetCode: 56. Merge Intervals(Medium)


下一篇:LeetCode 56. Merge Intervals 合并区间 (C++/Java)