# class Interval:
#     def __init__(self, a=0, b=0):
#         self.start = a
#         self.end = b
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param intervals Interval类一维数组 
# @return Interval类一维数组
#
class Solution:
    def merge(self , intervals: List[Interval]) -> List[Interval]:
        # write code here
        """
        1.数组进行排序
        排序之后
        设置指针 指向 第一个 p1和第二个p2
        比对 [start1:end1] [start2:end2]
        如果   end1 >=start2 合并 变成 [start1:end2]

        如果   end1 >=end2 合并 变成 [start1:end1]   移动p1  p2
        如果 end1 小于 start2  则将p1 指向的存入结果中 移动p1 移动p2 
      
        """
        res=[]
        if not  intervals:
            return res 
        if len(intervals)==1:
            return intervals
        p1=0
        p2=1
        n =len(intervals)
        intervals.sort(key=lambda x: x.start)
        while p2<n :
            #  小于第二个指针的开始
            if intervals[p1].end<intervals[p2].start:
                res.append(intervals[p1])
                
            elif intervals[p1].end>=intervals[p2].end:
                intervals[p2].start=intervals[p1].start # 合并
                intervals[p2].end=intervals[p1].end
            elif intervals[p1].end>=intervals[p2].start:
                intervals[p2].start=intervals[p1].start # 合并

            # 最后一个
            if p2==n-1:
                res.append(intervals[p2])
            p1+=1
            p2+=1

        return res