Python solution without sort


  • 0
    C

    My urgly olution without sort.

    def merge(self, intervals):
            l = len(intervals)
            if l <= 1: return intervals
            res = [intervals[0]]
            for i in intervals[1:]:
                if i.start > res[-1].end:
                    res.append(i)
                    continue
                if i.end < res[0].start: 
                    res.insert(0, i)
                    continue
                else:
                    if i.start < res[0].start: j = -1
                    else:
                        for j in range(len(res) - 1):
                            if res[j].start <= i.start < res[j + 1].start: break
                        else: 
                            res[-1].end = max(res[-1].end, i.end)
                            continue
                if j == -1:
                    res.insert(0, i)
                    j = 0
                elif i.start <= res[j].end:
                    res[j].end = max(res[j].end, i.end)
                else:
                    j += 1
                    res.insert(j, i)
                k = j + 1
                try:
                    while res[j].end >= res[k].start:
                        res[j].end = max(res[j].end, res[k].end)
                        del res[k]
                except IndexError, e: pass        
            return res

Log in to reply
 

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