Insert Interval

LeetCode

You are given an array of non-overlapping intervals intervals where intervals[i] = [start_i, end_i] represent the start and the end of the ith interval and intervals is sorted in ascending order by start_i. You are also given an interval newInterval = [start, end] that represents the start and end of another interval.

Insert newInterval into intervals such that intervals is still sorted in ascending order by start_i and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary).

Return intervals after the insertion.

Initial attempt

Time spent: 40m | Runtime: 75.33% | Memory: 32.50%

• This was one of the first problems I tried to do in this round of studying. I failed miserably and ended up looking up a solution.
• The problem was really just trying to make sense of the different cases. I have a tendency to overthink problems sometimes which probably made my performance that much worse.

Solution

• Copy over the intervals that don't overlap the new interval.
• Merge the intervals that do overlap the new interval.

Cleaned up code

Time spent: 16m | Runtime: 20.04% | Memory: 32.50%

class Solution:
    def insert(self, intervals, newInterval):
        new_start, new_end = newInterval
        results = []
        inserted = False
        for i, (start, end) in enumerate(intervals):
            if end < new_start:
                results.append([start, end])
            elif start > new_end:
                if not inserted:
                    inserted = True
                    results.append([new_start, new_end])
                results.append([start, end])
            else:
                if not inserted:
                    inserted = True
                    results.append([
                        min(new_start, start),
                        max(new_end, end),
                    ])
                results[-1][1] = max(results[-1][1], end)
        if not inserted:
            results.append([new_start, new_end])
        return results

This code is a bit clunky, but it does work. Here's a cleaner version.

Runtime: 14.32% | Memory: 72.18%

class Solution:
    def insert(self, intervals, newInterval):
        start, end = newInterval
        left = [
            interval for interval in intervals
            if interval[1] < start
        ]
        right = [
            interval for interval in intervals
            if interval[0] > end
        ]
        overlapped = (
            intervals[len(left):-len(right)]
            if len(right)
            else intervals[len(left):]
        )
        if overlapped:
            start = min(start, overlapped[0][0])
            end = max(end, overlapped[-1][1])
        return left + [[start, end]] + right

There are probably still ways to massage this, but it's probably not much more interesting to do so.