MUYANG GUO / INDEX

LeetCode

LintCode 839 Merge Two Sorted Interval Lists - Easy

839. Merge Two Sorted Interval Lists

·1 min read·#LintCode#Easy#Python

839. Merge Two Sorted Interval Lists — Easy

Open on LintCode

Problem

  1. Merge Two Sorted Interval Lists

Merge two sorted (ascending) lists of interval and return it as a new sorted list. The new sorted list should be made by splicing together the intervals of the two lists and sorted in ascending order.

Example Example1

Input: list1 = [(1,2),(3,4)] and list2 = [(2,3),(5,6)] Output: [(1,4),(5,6)] Explanation: (1,2),(2,3),(3,4) --> (1,4) (5,6) --> (5,6) Example2

Input: list1 = [(1,2),(3,4)] and list2 = [(4,5),(6,7)] Output: [(1,2),(3,5),(6,7)] Explanation: (1,2) --> (1,2) (3,4),(4,5) --> (3,5) (6,7) --> (6,7) Notice The intervals in the given list do not overlap. The intervals in different lists may overlap.

Solution

### 双指针做法，类似于merge two sorted lists:
 
"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""
 
class Solution:
    """
    @param list1: one of the given list
    @param list2: another list
    @return: the new sorted list of interval
    """
    def mergeTwoInterval(self, list1, list2):
        # write your code here
        i, j = 0, 0
        intervals = []
        while i < len(list1) and j < len(list2):
            if list1[i].start < list2[j].start:
                self.push_back(intervals, list1[i])
                i += 1
            else:
                self.push_back(intervals, list2[j])
                j += 1
        while i < len(list1):
            self.push_back(intervals, list1[i])
            i += 1
        while j < len(list2):
            self.push_back(intervals, list2[j])
            j += 1
        
        return intervals
        
    def push_back(self, intervals, interval):
        if not intervals:
            intervals.append(interval)
            return
        
        last_interval = intervals[-1]
        if last_interval.end < interval.start:
            intervals.append(interval)
            return
        
        intervals[-1].end = max(intervals[-1].end, interval.end)

Comments