7+ lines, 3 easy solutions


  • 71

    Solution 1: (7 lines, 88 ms)

    Collect 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.

    def insert(self, intervals, newInterval):
        s, e = newInterval.start, newInterval.end
        left = [i for i in intervals if i.end < s]
        right = [i for i in intervals if i.start > e]
        if left + right != intervals:
            s = min(s, intervals[len(left)].start)
            e = max(e, intervals[~len(right)].end)
        return left + [Interval(s, e)] + right
    

    Solution 2: (8 lines, 84 ms)

    Same algorithm as solution 1, but different implementation with only one pass and explicitly collecting the to-be-merged intervals.

    def insert(self, intervals, newInterval):
        s, e = newInterval.start, newInterval.end
        parts = merge, left, right = [], [], []
        for i in intervals:
            parts[(i.end < s) - (i.start > e)].append(i)
        if merge:
            s = min(s, merge[0].start)
            e = max(e, merge[-1].end)
        return left + [Interval(s, e)] + right
    

    Solution 3: (11 lines, 80 ms)

    Same again, but collect and merge while going over the intervals once.

    def insert(self, intervals, newInterval):
        s, e = newInterval.start, newInterval.end
        left, right = [], []
        for i in intervals:
            if i.end < s:
                left += i,
            elif i.start > e:
                right += i,
            else:
                s = min(s, i.start)
                e = max(e, i.end)
        return left + [Interval(s, e)] + right

  • 3

    It is always a pleasure to read your Python codes. :-) The parts[(i.end < s) - (i.start > e)].append(i) in Solution 2 is damn clever!


  • 1

    Yeah, I like that one a lot. Came up with it a while back and I'm happy every time I can use it :-)


  • 1
    S

    Great solutions! I always learn something new about Python when I read your code. So smart!


  • 5
    I

    I wrote my own solution earlier but looking at your solution, it makes it much easier to read/understand the code. I think simpler solution is always much better and easier to get it right especially at the time of interview. Thank you very much for sharing your solution.

    Here is basically my way of translating your solutions into C++.

    vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
        vector<Interval> left, right;
        for (int i = 0; i < intervals.size(); i++) {
            if (intervals[i].end < newInterval.start) {
                left.push_back(intervals[i]);
            }
            if (intervals[i].start > newInterval.end) {
                right.push_back(intervals[i]);
            }
        }
        int s = newInterval.start, e = newInterval.end;
        if ((left.size()+right.size()) != intervals.size()) {
            s = min(s, intervals[left.size()].start);
            e = max(e, intervals[intervals.size()-right.size()-1].end);
        }
        Interval middle(s,e);
        left.push_back(middle);
        left.insert(left.end(), right.begin(), right.end());
        return left;
    }
    

  • 0
    S

    I've learned python 3 years and this is my first time to see syntax like ~9, awesome.


  • 0
    Y

    Very beautiful!


  • 0

    Thanks for the awesome and clean solutions!

    I think in the 3rd solution, it should be left += [i] instead of left += i? So is that of right += i.


  • 0

    @atomake I'm not doing left += i.


  • 0

    @StefanPochmann My bad. There is a comma. it is left += i, then.

    May I ask what's such usage called? It does the same as append() but I guess there are some performance concerns?


  • 2

    @atomake said in 7+ lines, 3 easy solutions:

    May I ask what's such usage called?

    I don't know whether the usage is called something. What I'm using is the comma operator, and it creates a tuple.

    I think sometimes it looks nicer than append (thanks to the spaces around +=), I think it's slightly faster in one of Python 2 or 3 (can never remember which one), and I want to make people aware of the comma operator :-)


  • 1
    O

    4-liner in Python:

    class Solution(object):
        def insert(self, intervals, newInterval):
            starts, ends = [x.start for x in intervals], [x.end for x in intervals]
            i, j = bisect.bisect_left(ends, newInterval.start), bisect.bisect_right(starts, newInterval.end)
            intervals[i:j] = [newInterval] if i==j else [Interval(min(newInterval.start,starts[i]), max(newInterval.end,ends[j-1]))]
            return intervals
    

  • 0
    S

    @StefanPochmann

    Easy to understand Python code below. Add newInterval to the existing intervals and keep merging.

        intervals = sorted(intervals+[newInterval], key = lambda x: x.start)
        output = [intervals[0]]
        for i in xrange(1, len(intervals)):
            if intervals[i].start <= output[-1].end:
                output[-1] = Interval(output[-1].start, max(intervals[i].end, output[-1].end))
            else:
                output.append(intervals[i])
        return output

  • 0
    S

    very elegant code, a small comment that I have is that you can do this without creating multiple lists and needing to merge them which creates a new list. Here is what I did.
    """"
    def insert(self, intervals, newInterval):
    new_intervals = []
    new_begin = newInterval.start
    new_end = newInterval.end

        last_index = 0
        for index in range(len(intervals)):
            interval = intervals[index]
           
            if interval.start > new_end:
                last_index = index
                break
                
            last_index = index + 1
            if new_begin <= interval.end:
                new_begin = min(interval.start,new_begin)
                new_end = max(interval.end, new_end)
            else:                    
                new_intervals.append(interval)
    
        new_intervals.append(Interval(new_begin, new_end))
        for i in range(last_index,len(intervals)):
            new_intervals.append(intervals[i])                    
        return new_intervals
    

    """"""""""
    This runs in 65 ms vs 80 ms, a bit faster.


  • 0
    L

    parts[(i.end < s) - (i.start > e)].append(i)

    Magnificent!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.