'''
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, 
and return an array of the non-overlapping intervals that cover all the intervals in the input.

 

Example 1:

Input: intervals = [[1,3],[8,10],[2,6],[15,18]]

'''

class Solution(object):
    def mergeIntervals(self, intervals:list[list[int]]):
        #sort the list of list of intervals by the first value 1, 2, 8, 15
        intervals.sort(key = lambda i: i[0])
        output = [intervals[0]] # initialize the list of list output = [[1, 3]]  initially, then we append
        print(intervals)
        print(f'Initially the output is: {output}')
        for start, end in intervals[1:]: #loop intervals starting from the [1] because above u can see we already have the first  inner list [0]
            lastEnd = output[-1][1] #obtains the newest added inteval in the list gets the end val first iteration [[1, 3]] it would be 3
            if start <= lastEnd: # if 2 <= 3 it means they cross so we  need to merge
                output[-1][1] = max(lastEnd, end) #the latest from the list new value will be the max of the curr value [1, 3] (3) vs [2, 6] (6) .. 
                                                  #6 is the max between those two so that is the new value. im only explaining the first iteration 
            else:
                output.append([start, end])
        return output
            
        
if __name__ == '__main__':
    intervals = [[1,3],[8,10],[2,6],[15,18]]
    obj1 = Solution()

    print(obj1.mergeIntervals(intervals))
#----------output-----------
'''
    [[1, 3], [2, 6], [8, 10], [15, 18]]
    Initially the output is: [[1, 3]]  
    [[1, 6], [8, 10], [15, 18]] 
'''