LeetCode Day 36 Greedy Algorithm (5/6)

The 5th practice, questions begin a little difficult!

Question 1

435. Non-overlapping Intervals

Given an array of intervals intervals where intervals[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

To remove the overlap, the first thing to do is to sort to get the intervals to overlap as much as possible. Then find the minimum value of the right boundary. This is a similar idea to yesterday’s question (LC452), so you can modify it slightly.

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals:
            return 0
        
        intervals.sort(key=lambda x: x[0])  
        result = 1  
        for i in range(1, len(intervals)):
            if intervals[i][0] >= intervals[i - 1][1]:  
                result += 1
            else:  
                intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])  
        
        return len(intervals) - result

Question 2

763. Partition Labels

You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.

Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.

Return a list of integers representing the size of these parts.

The first time I did this kind of question, there is no idea.

I read the answer given by others: in the process of traversal is equivalent to find the boundary of each letter, if you find the furthest boundary of all the letters previously traversed, that this boundary is the split point. At this point, all the letters that have appeared before, the farthest to this boundary.

It can be divided into two steps as follows:

Count the last occurrence of each character Iterate through the characters from the beginning, and update the farthest occurrence of the character’s subscript, if we find the farthest occurrence of the character’s subscript and the current subscript is equal, then we have found the split point.

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        last_occurrence = {}  
        for i, ch in enumerate(s):
            last_occurrence[ch] = i
 
        result = []
        start = 0
        end = 0
        for i, ch in enumerate(s):
            end = max(end, last_occurrence[ch])  
            if i == end:  
                result.append(end - start + 1)
                start = i + 1
 
        return result

Question 3

56. Merge Intervals

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.

Pretty much the same idea as the previous questions, still sorting first and then looking at the overlap at the boundary places.

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        result = []
        if len(intervals) == 0:
            return result  
        intervals.sort(key=lambda x: x[0])  
        result.append(intervals[0])  
        for i in range(1, len(intervals)):
            if result[-1][1] >= intervals[i][0]:  
         
                result[-1][1] = max(result[-1][1], intervals[i][1])
            else:
                result.append(intervals[i])  
 
        return result