# Greedy algorithm

## What is Greedy algorithm

Greedy is an algorithmic paradigm that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. So the problems where choosing locally optimal also leads to global solution are the best fit for Greedy.

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

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

1 | Input: prices = [7,1,5,3,6,4] |

Example 2:

1 | Input: prices = [1,2,3,4,5] |

Example 3:

1 | Input: prices = [7,6,4,3,1] |

Constraints:

- 1 <= prices.length <= 3 * 104
- 0 <= prices[i] <= 104

Solution:

1 | class Solution: |

## [Leetcode 134] Gas Station

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Example 1:

1 | Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2] |

Example 2:

1 | Input: gas = [2,3,4], cost = [3,4,3] |

Constraints:

- n == gas.length == cost.length
- 1 <= n <= 105
- 0 <= gas[i], cost[i] <= 104

Solution:

1 | class Solution: |

## [Leetcode 135] Candy

There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.

You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

Return the minimum number of candies you need to have to distribute the candies to the children.

Example 1:

1 | Input: ratings = [1,0,2] |

Example 2:

1 | Input: ratings = [1,2,2] |

Constraints:

- n == ratings.length
- 1 <= n <= 2 * 104
- 0 <= ratings[i] <= 2 * 104

Solution:

1 | class Solution: |

## [Leetcode 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.

Example 1:

1 | Input: intervals = [[1,2],[2,3],[3,4],[1,3]] |

Example 2:

1 | Input: intervals = [[1,2],[1,2],[1,2]] |

Example 3:

1 | Input: intervals = [[1,2],[2,3]] |

Constraints:

- 1 <= intervals.length <= 105
- intervals[i].length == 2
- -5 * 104 <= starti < endi <= 5 * 104

Solution:

1 | class Solution: |

## [Leetcode 452] Minimum Number of Arrows to Burst Balloons

There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.

Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.

Given the array points, return the minimum number of arrows that must be shot to burst all balloons.

Example 1:

1 | Input: points = [[10,16],[2,8],[1,6],[7,12]] |

Example 2:

1 | Input: points = [[1,2],[3,4],[5,6],[7,8]] |

Example 3:

1 | Input: points = [[1,2],[2,3],[3,4],[4,5]] |

Constraints:

- 1 <= points.length <= 105
- points[i].length == 2
- -231 <= xstart < xend <= 231 - 1

Solution:

1 | class Solution: |

## [Leetcode 659] Split Array into Consecutive Subsequences

You are given an integer array nums that is sorted in non-decreasing order.

Determine if it is possible to split nums into one or more subsequences such that both of the following conditions are true:

- Each subsequence is a consecutive increasing sequence (i.e. each integer is exactly one more than the previous integer).
- All subsequences have a length of 3 or more.

Return true if you can split nums according to the above conditions, or false otherwise.

A subsequence of an array is a new array that is formed from the original array by deleting some (can be none) of the elements without disturbing the relative positions of the remaining elements. (i.e., [1,3,5] is a subsequence of [1,2,3,4,5] while [1,3,2] is not).

Example 1:

1 | Input: nums = [1,2,3,3,4,5] |

Example 2:

1 | Input: nums = [1,2,3,3,4,4,5,5] |

Example 3:

1 | Input: nums = [1,2,3,4,4,5] |

Constraints:

- 1 <= nums.length <= 104
- -1000 <= nums[i] <= 1000
- nums is sorted in non-decreasing order.

Solution:

1 | class Solution: |