greedy Archives - shawnlyu

August 26, 2020August 26, 2020

[Leetcode]714. Best Time to Buy and Sell Stock with Transaction Fee

This series of Buy and Sell Stock I~VI on Leetcode is a great practice for Dynamic Programming – State Machine. Therefore I prepared blogs for each of them and hopefully it would help you to understand them better. You can find the relations of them at the bottom and feel free to leave any comments.

August 21, 2020August 26, 2020

[Leetcode]122. Best Time to Buy and Sell Stock II

August 21, 2020August 26, 2020

[Leetcode]121. Best Time to Buy and Sell Stock

July 28, 2020July 29, 2020

[Leetcode]621. Task Scheduler

You are given a char array representing tasks CPU need to do. It contains capital letters A to Z where each letter represents a different task. Tasks could be done without the original order of the array. Each task is done in one unit of time. For each unit of time, the CPU could complete either one task or just be idle.
However, there is a non-negative integer n that represents the cooldown period between two same tasks (the same letter in the array), that is that there must be at least n units of time between any two same tasks.
You need to return the least number of units of times that the CPU will take to finish all the given tasks.

July 22, 2020July 25, 2020

[Leetcode]1520. Maximum Number of Non-Overlapping Substrings

Given a string s of lowercase letters, you need to find the maximum number of non-emptysubstrings of s that meet the following conditions:
The substrings do not overlap, that is for any two substrings s[i..j] and s[k..l], either j < k or i > l is true.
A substring that contains a certain character c must also contain all occurrences of c.
Find the maximum number of substrings that meet the above conditions. If there are multiple solutions with the same number of substrings, return the one with minimum total length. It can be shown that there exists a unique solution of minimum total length.
Notice that you can return the substrings in any order.

July 22, 2020July 22, 2020

Find maximum meetings in one room

There is one meeting room in a firm. There are N meetings in the form of (S[i], F[i]) where S[i] is the start time of meeting i and F[i] is finish time of meeting i. The task is to find the maximum number of meetings that can be accommodated in the meeting room. Print all meeting numbers
Examples:
Input : s[] = {1, 3, 0, 5, 8, 5}, f[] = {2, 4, 6, 7, 9, 9}
Output : 1 2 4 5
First meeting [1, 2]
Second meeting [3, 4]
Fourth meeting [5, 7]
Fivth meeting [8, 9]

July 22, 2020July 25, 2020

[Leetcode]253. Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (s_i < e_i), find the minimum number of conference rooms required.
Example 1:
Input: [[0, 30],[5, 10],[15, 20]] Output: 2

June 22, 2020June 26, 2020

[Leetcode problems]1488. Avoid Flood in The City

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over the nth lake, the nth lake becomes full of water. If it rains over a lake which is full of water, there will be a flood. Your goal is to avoid the flood in any lake.
Given an integer array rains where:
rains[i] > 0 means there will be rains over the rains[i] lake.
rains[i] == 0 means there are no rains this day and you can choose one lake this day and dry it.
Return an array ans where:
ans.length == rains.length
ans[i] == -1 if rains[i] > 0.
ans[i] is the lake you choose to dry in the ith day if rains[i] == 0.
If there are multiple valid answers return any of them. If it is impossible to avoid flood return an empty array.
Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)
 
Example 1:
Input: rains = [1,2,3,4] Output: [-1,-1,-1,-1]
Example 2:
Input: rains = [1,2,0,0,2,1] Output: [-1,-1,2,1,-1,-1]