7+ lines, 3 easy solutions
Solution 1: (7 lines, 88 ms)\n\nCollect the intervals strictly left or right of the new interval, then merge the new one with the middle ones (if any) before in
**Solution 1:** (7 lines, 88 ms)\n\nCollect the intervals strictly left or right of the new interval, then merge the new one with the middle ones (if any) before inserting it between left and right ones.\n\n    def insert(self, intervals, newInterval):\n        s, e = newInterval.start, newInterval.end\n        left = [i for i in intervals if i.end < s]\n        right = [i for i in intervals if i.start > e]\n        if left + right != intervals:\n            s = min(s, intervals[len(left)].start)\n            e = max(e, intervals[~len(right)].end)\n        return left + [Interval(s, e)] + right\n\n---\n\n**Solution 2:** (8 lines, 84 ms)\n\nSame algorithm as solution 1, but different implementation with only one pass and explicitly collecting the to-be-merged intervals.\n\n    def insert(self, intervals, newInterval):\n        s, e = newInterval.start, newInterval.end\n        parts = merge, left, right = [], [], []\n        for i in intervals:\n            parts[(i.end < s) - (i.start > e)].append(i)\n        if merge:\n            s = min(s, merge[0].start)\n            e = max(e, merge[-1].end)\n        return left + [Interval(s, e)] + right\n\n---\n\n**Solution 3:** (11 lines, 80 ms)\n\nSame again, but collect and merge while going over the intervals once.\n\n    def insert(self, intervals, newInterval):\n        s, e = newInterval.start, newInterval.end\n        left, right = [], []\n        for i in intervals:\n            if i.end < s:\n                left += i,\n            elif i.start > e:\n                right += i,\n            else:\n                s = min(s, i.start)\n                e = max(e, i.end)\n        return left + [Interval(s, e)] + right
['Python']