Python O(n) and O(nlgn) solutions.
    \n    \n    # O(nlgn) time, the same as Merge Intervals \n    # https://leetcode.com/problems/merge-intervals/\n    def insert1(self, intervals, newInterval
        \n    \n    # O(nlgn) time, the same as Merge Intervals \n    # https://leetcode.com/problems/merge-intervals/\n    def insert1(self, intervals, newInterval):\n        intervals.append(newInterval)\n        res = []\n        for i in sorted(intervals, key=lambda x:x.start):\n            if res and res[-1].end >= i.start:\n                res[-1].end = max(res[-1].end, i.end)\n            else:\n                res.append(i)\n        return res\n        \n    # O(n) time, not in-place, make use of the \n    # property that the intervals were initially sorted \n    # according to their start times\n    def insert(self, intervals, newInterval):\n        res, n = [], newInterval\n        for index, i in enumerate(intervals):\n            if i.end < n.start:\n                res.append(i)\n            elif n.end < i.start:\n                res.append(n)\n                return res+intervals[index:]  # can return earlier\n            else:  # overlap case\n                n.start = min(n.start, i.start)\n                n.end = max(n.end, i.end)\n        res.append(n)\n        return res
['Python']