LeetCode 57

💡 Data Structure and Algorithm Practice

57. Insert Interval

Possible Algorithms

• Greedy
• Intervals

class Solution:
    def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:
#         res = []
#         block = None
#         for slot in intervals:
#             if newInterval[0] <= slot[1] <= newInterval[1]:
#                 if slot[0] < newInterval[0]:
#                     block = slot
#                 else:
#                     block = newInterval
                    
#                 if slot[1] < newInterval[1]:
#                     block[1] = newInterval[1]
#                 else:
#                     block[1] = slot[1]
#             else:
#                 if newInterval[1] < slot[0]:
#                     res.append(block)
#                 res.append(slot)
            
#         print(f'block: {block}')
#         print(f'res: {res}')
        
#         return res
    
        
#         res = []
#         block = None
#         for slot in intervals:
#             if slot[1] < newInterval[0] or slot[0] > newInterval[1]:
#                 res.append(slot)
#             else:
#                 if newInterval[0] <= slot[1] <= newInterval[1]:
#                     block = [min(slot[0], newInterval[0]), max(slot[1], newInterval[1])]

#                 if newInterval[0] <= slot[0] <= newInterval[1]:
#                     block = [min(slot[0], newInterval[0]), max(slot[1], newInterval[1])]
            
#             print(f'block: {block}')
#             print(f'res: {res}')
        
        res = []

        for i in range(len(intervals)):
            if newInterval[1] < intervals[i][0]:
                res.append(newInterval)
                return res + intervals[i:]
            elif newInterval[0] > intervals[i][1]:
                res.append(intervals[i])
            else:
                newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]

        res.append(newInterval)
        return res
            

Approach

1. Check every possible cases.
2. Think of key idea - e.g. newInterval = [min(newInterval[0], intervals[i][0]), max(newInterval[1], intervals[i][1])]
3. Write a pseudocode.
4. Code.