Greedy strategy¶

Greedy strategy is a common algorithmic idea. Specifically, it means that when solving a problem, always make the best choice in the current view. In other words, it is not considered from the overall optimum. What he made was a local optimal solution in a sense. Greedy algorithm does not get the overall optimal solution to all problems, such as coin change problem, the key is the choice of greedy strategy.

The selected greedy strategy must have no aftereffect, that is, the previous process of a certain state will not affect the later state, and is only related to the current state, which is the same as dynamic programming. Greedy strategy is similar to dynamic programming. In most cases, it is also used to deal with the extreme value problem.

There are 73 questions about greedy strategies on LeetCode. We divide it into several types to explain. As of now, we only provide coverage questions. For other types, you can look forward to my new book or future problem solving articles.

Coverage issues¶

We choose three questions to explain. In addition to using the greedy method, you can also try dynamic programming to solve these three questions.

-45. Jumping Game II, difficult -1024. Video Stitching, medium -1326. Minimum number of taps to irrigate the garden, difficult

A major feature of the coverage problem, we can abstract it as a large interval I on a given number axis and n cells i[0], i[1], ..., i[n-1], ask At least how many cells are selected, so that the union of these cells can cover the entire large interval.

Let's take a look at these three questions.

45. Jumping Game II¶

Title description¶

Given an array of non-negative integers, you are initially at the first position of the array.

Each element in the array represents the maximum length you can jump at that position.

Your goal is to use the least number of jumps to reach the last position of the array.

Example:

Input: [2,3,1,1,4]
Output: 2
Explanation: The minimum number of jumps to jump to the last position is 2.
  Jump from subscript 0 to the position of subscript 1, skip 1 step, and then skip 3 steps to reach the last position of the array.
Description:

Suppose you can always reach the last position of the array.

Ideas¶

Here we use the greedy strategy to solve. That is, each time you choose a location that can jump farther within the jumpable range.

As shown in the figure below, the starting position is 2, and the jumpable range is the orange node. Since 3 can jump farther, enough to cover the situation of 2, so you should jump to the 3 position.

When we jump to the 3 position. As shown in the figure below, the range that can be jumped is orange 1, 1, 4. Since 4 can jump farther, jump to the 4 position.

When writing code, we can use end to indicate the boundary of the current jump, corresponding to orange 1 in the first picture and orange 4 in the second picture. And when traversing the array, when the boundary is reached, the boundary is updated again.

Picture from https://leetcode-cn.com/u/windliang/

Code¶

Code support: Python3

Python3 Code:

class Solution:
    def jump(self, nums: List[int]) -> int:
        n, cnt, furthest, end = len(nums), 0, 0, 0
        for i in range(n-1):
            furthest = max(furthest, nums[i] + i)
            if i == end:
                cnt += 1
                end = furthest

        return cnt

Complexity Analysis

-Time complexity: \(O(N)\).

-Space complexity: \(O(1)\).

1024. Video stitching¶

Title description¶

You will get a series of video clips from a sporting event that lasts T seconds. These fragments may overlap, or they may vary in length.

Video clips clips[i] are all represented by intervals: start at clips[i][0] and end at clips[i][1]. We can even edit these segments freely. For example, segment [0, 7] can be cut into three parts [0, 1] + [1, 3] + [3, 7].

We need to re-edit these segments and splice the edited content into segments ([0, T]) covering the entire movement process. Return the minimum number of fragments required, or -1 if the task cannot be completed.

Example 1:

Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
Output: 3
Explanation:
We select the three segments [0,2], [8,10], [1,9].
Then, reproduce the game segment according to the following scheme:
Edit [1,9] again into [1,2] + [2,8] + [8,9].
Now we have [0,2] + [2,8] + [8,10], and these cover the entire game [0, 10].
Example 2:

Input: clips = [[0,1],[1,2]], T = 5
Output: -1
Explanation:
We cannot just use [0,1] and [0,2] to cover the entire process of [0,5].
Example 3:

Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1, 3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9] ], T = 9
Output: 3
Explanation:
We select segments [0,4], [4,7] and [6,9].
Example 4:

Input: clips = [[0,4],[2,8]], T = 5
Output: 2
Explanation:
Note that you may record a video past the end of the game.

prompt:

1 <= clips.length <= 100
0 <= clips[i][0], clips[i][1] <= 100
0 <= T <= 100

Ideas¶

Here we still use the greedy strategy to solve. The idea of the previous question is to maintain a furthest, end variable and constantly update it greedy. The same is true for this question. The difference is that the data for this question is a two-dimensional array. But if you thoroughly understand the above question, I think this question will not trouble you.

Let's see how similar this question is to the above question.

Take the data given by the title as an example: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6 ,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7 ],[6,9]], T = 9

We sort the original array by start time, and look at the previous part first: [[0,1], [0,2], [0,3], [0,4], [1,3], [1 ,4], [2,5], [2,6], ...]

Note that it does not need to be sorted, but is similar to the idea of bucket sorting, using extra space, refer to the code area for details

Is this equivalent to the above jumping game: [4,0,2]. So far we have successfully converted this question into the question already made above. There is only one difference, that is, the above question is guaranteed to skip to the end, and this question may not be spelled out. Therefore, this critical value needs to be paid attention to. Please refer to the code area behind for details.

Code¶

Code support: Python3

Python3 Code:

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        furthest = [0] * (T)

        for s, e in clips:
            for i in range(s, e + 1):
                # No need to consider, this is why I can create a furthest array of size T
                if i >= T:break
                furthest[i] = max(furthest[i], e)
        # After the above preprocessing, the gap between this question and the above question is very small
        # The last here is equivalent to the furthest of the previous question
        end = last = ans = 0
        for i in range(T):
            last = max(last, furthest[i])
            # A more critical value than the above question
            if last == i: return-1
            if end == i:
                ans += 1
                end = last
        return ans

Complexity Analysis

-Time complexity: \(O(\sum_{i=1}^{n}ranges[i] + T)\), where ranges[i] is the interval length of clips[i].

-Space complexity: \(O(T)\).

1326. Minimum number of taps to irrigate the garden¶

Title description¶

There is a one-dimensional garden on the x-axis. The length of the garden is n, starting at point 0 and ending at point n.

There are a total of n + 1 taps in the garden, located at [0, 1, ..., n].

Give you an integer n and an integer array of length n + 1 ranges, where ranges[i] (subscript starting from 0) means: if you turn on the faucet at point i, the area that can be irrigated is [i-ranges[i ], i + ranges[i]].

Please return the minimum number of taps that can irrigate the entire garden. If there is always a place in the garden that cannot be irrigated, please return -1.

Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation:
The tap at point 0 can irrigate the interval [-3,3]
The tap at point 1 can irrigate the interval [-3,5]
The tap at point 2 can irrigate the interval [1,3]
The tap at point 3 can irrigate the interval [2,4]
The tap at point 4 can irrigate the interval [4,4]
The tap at point 5 can irrigate the interval [5,5]
Just turn on the faucet at point 1 to irrigate the entire garden [0,5].
Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you turn on all the taps, you can't irrigate the entire garden.
Example 3:

Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3
Example 4:

Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2
Example 5:

Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1

prompt:

1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100

Ideas¶

The idea is still the same as the above question. We still adopt the greedy strategy, continue to follow the above ideas, try to find the faucet that can cover the farthest (right) position, and record the land it covers on the far right.

I won't explain much here, let's take a look at the specific algorithm, and everyone will experience how similar it is.

algorithm:

-Use furthest[i] to record the rightmost land that can be covered by each tap i. There are a total of n+1 faucets, and we traverse it n+1 times. -Calculate and update the left and right boundaries of the faucet every time [i-ranges[i], i + ranges[i]] the furthest of the faucet in the range -Finally, starting from land 0, traversing to land n, recording the number of taps, similar to a jumping game.

Is it almost the same as the above question?

Code¶

Code support: Python3

Python3 Code:

class Solution:
    def minTaps(self, n: int, ranges: List[int]) -> int:
        furthest, ans, cur = [0] * n, 0, 0
        # Preprocessing
        for i in range(n + 1):
            for j in range(max(0, i-ranges[i]), min(n, i + ranges[i])):
                furthest[j] = max(furthest[j], min(n, i + ranges[i]))
        # Old routine
        end = last = 0
        for i in range(n):
            if furthest[i] == 0: return -1
            last = max(last, furthest[i])
            if i == end:
                end = last
                ans += 1
        return ans

Complexity Analysis

-Time complexity: \(O(\sum_{i=1}^{n}R[i] + n)\), where R[i] is the interval length of ranges[i].

-Space complexity: \(O(n)\).

to sum up¶

For extreme value problems, we can consider using dynamic programming and greedy, while it is okay to use dynamic programming and greedy for covering problems, but the code and complexity of using greedy are usually simpler. But correspondingly, the difficulty of greedy lies in how to prove that the local optimal solution can get the global optimal solution. Through the study of these questions, I hope you can understand the routines of covering questions, and the bottom layer is the same. Understand this, if you go back and look at the coverage topic, you may discover a new world.