Short Ruby and Python


  • 17

    Which interval would be the best first (leftmost) interval to keep? One that ends first, as it leaves the most room for the rest. So take one with smallest end, remove all the bad ones overlapping it, and repeat (taking the one with smallest end of the remaining ones). For the overlap test, just keep track of the current end, initialized with negative infinity.

    Ruby

    Take out intervals as described above, so what's left is the bad overlapping ones, so just return their number.

    def erase_overlap_intervals(intervals)
      end_ = -1.0 / 0
      intervals.sort_by(&:end).reject { |i|
        end_ = i.end if i.start >= end_
      }.size
    end
    

    Alternatively, i.start >= end_ and end_ = i.end works, too.

    Python

    def eraseOverlapIntervals(self, intervals):
        end = float('-inf')
        erased = 0
        for i in sorted(intervals, key=lambda i: i.end):
            if i.start >= end:
                end = i.end
            else:
                erased += 1
        return erased

  • 0
    N

    I personally prefer to initialize an infinitely small number with None, because None is smaller than any number. Is it a good idea or bad idea?


  • 0

    @NoAnyLove I think it's bad. It's not terribly natural, it's not in the Python specification but only an implementation detail of the current CPython implementation, and in Python 3 it was removed.

    http://stackoverflow.com/a/3270689/1672429
    http://stackoverflow.com/a/2384139/1672429


  • 0
    N

    @StefanPochmann I see, thanks a lot.


  • 0

    @NoAnyLove On the other hand, I did just abuse it in a solution for another problem. It was just too convenient, and that solution isn't serious anyway :-)


  • 0

    1 linear version:

    def eraseOverlapIntervals(self, intervals):
            return len(intervals) - reduce(lambda res, i: (res[0] + 1, i.end) if i.start >= res[1] else res,
                                           sorted(intervals, key=lambda i: i.end), (0, -float('inf')))[0]

  • 0
    S
    This post is deleted!

Log in to reply
 

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