# class Interval(object): # def __init__(self, s=0, e=0): # self.start = s # self.end = e class Solution(object): def merge(self, intervals): """ :type intervals: List[Interval] :rtype: List[Interval] """ if intervals == : return  # Find max value mx = -1 * float("inf") for i in intervals: mx = max(max(i.start, i.end), mx) # Create array of that length. Array represents the whole span # of time which can be blocked into intervals res =  * (mx+1) for i in intervals: # If an interval is just one spot and is not part of any other # interval, mark it with a 2 if i.start == i.end: if res[i.end]==0: res[i.end] = 2 else: # Mark the slot an interval fills with all 1s except for the last spot res[i.start:i.end] =  * (i.end - i.start) # If the last spot is not part of an existing interval # set it to -1 if res[i.end]!=1: res[i.end] = -1 result =  i = 0 # iterates over time array. Saves continuous blocks of 1s as intervals # Saves 2s as a single interval block on their own while i < len(res): if res[i] == 1: start = i while res[i] == 1: i += 1 end = i - 1 result.append(Interval(start, end+1)) elif res[i] == 2: result.append(Interval(i, i)) i += 1 return result
You are wrong.
Take the time of space allocation into account, time complexity can be no smaller than space complexity.
@lv.zheng.2015 Initializing a python list of a certain size takes roughly constant time:
python -m timeit -n 1000 -s "*100" 1000 loops, best of 3: 0.01 usec per loop python -m timeit -n 1000 -s "*1000" 1000 loops, best of 3: 0.011 usec per loop python -m timeit -n 1000 -s "*100000" 1000 loops, best of 3: 0.011 usec per loop python -m timeit -n 1000 -s "*1000000" 1000 loops, best of 3: 0.0119 usec per loop
Also, in python I believe replacing a subset of a list with another list as I am doing takes O(1), as the internal list implementation uses a doubly linked list, see Python list documentation. So it should still be O(n) time complexity.