Insert, sort and merge. It is very similar with last problem.
Solution:
# T:O(N) S:O(n) class Solution: # @param {Interval[]} intervals # @param {Interval} newInterval # @return {Interval[]} def insert(self, intervals, newInterval): intervals.append(newInterval) def merge(intervals): intervals.sort(key = lambda x: x.start) N, ret = len(intervals), [] for i in xrange(N): if not ret: ret.append(intervals[i]) else: L = len(ret) if ret[L-1].start<=intervals[i].start<=ret[L-1].end: ret[L-1].end = max(intervals[i].end, ret[L-1].end) else: ret.append(intervals[i]) return ret a = merge(intervals) return aRun Time: 108 ms
No comments:
Post a Comment