Simple Python solution


  • 0
    Y
    #
    # O(n * log n) time algorithm returning minimal number of intervals to remove to create disjoint intervals
    def n_erased(ivals):
        if not ivals:
            return 0
        ivals.sort(key=lambda ival: ival.start)
        erased = 0
        last = ivals[0]
        for ival in ivals[1:]:
            if ival.start >= last.end:
                last = ival
                continue
            erased += 1
            # remove the interval that ends later
            if ival.end <= last.end:
                last = ival
        return erased
    

Log in to reply
 

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