 # Greedy Algorithm Problem With Solution Set-1

I am starting a series where we will discuss problems on the Greedy Algorithm along with their solution and explanation. We will start from easy Leetcode that are based on greedy algorithm problem first and accordingly, we will increase the level.

Today I am going to discuss two problems based on Greedy Algorithms. The problems are easy to level problems but they are useful in understanding the Algorithm better.

## Leetcode 1029 : Two City Scheduling

There are 2N people a company is planning to interview. The cost of flying the ith person to city A is cost[i] and the cost of flying the ith person to city Bis cost[i].

Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

Example 1:

Input: [[10,20],[30,200],[400,50],[30,20]]
Output: 110

Explanation: The first person goes to city A for a cost of 10. The second person goes to city A for a cost of 30. The third person goes to city B for a cost of 50. The fourth person goes to city B for a cost of 20. The total minimum cost is 10 + 30 + 50 + 20 = 110 to have half the people interviewing in each city.

Note:
1 <= costs.length <= 100
It is guaranteed that costs.length is even
1 <= costs[i], costs[i] <= 100

### Analysis of Problem Statement

So, let us understand the problem statement more clearly, there are 2N people in a company and they all have to travel to two cities (let say city A and B) for their work.

The travel cost of each person to both cities are given. You have to pick N people for each city such that cost of travel is minimum.

Here our constraint is travel cost and we have to minimise it.

Let us understand take few examples,

In the above example, there are 4 people in a company and travel cost of all employee to cities A (yellow) and B (green) are given respectively.

Output : 110

The 1st and 2nd person visit city A at the cost of 40 (10+30) and 3rd and 4th person visit city B at the cost of 70 (50+20).

NOTE, since N = 4 in the above case, 2 employees visit city A and 2 visit city B.

Let’s take another example,

In this example also, there are 4 people in a company and for every employee traveling to city A is cheaper than city B but we can’t send every employee to city A.

We have to make sure that two people will travel to city A and two people will travel to city B at a minimum cost.

Output : 20 + 15 + 40 + 30 = 105

This is the minimum cost where we sent 1st & 4th employee to city B and 2nd & 3rd to city A.

Hope Problem statement is clear to you, it is highly recommended please try it yourself before moving to the solution.[greedy algorithm problem]

### Approach to the Problem

Let us discuss how you will approach this greedy algorithm problem because my motive is not to just post you the solution, I want you all to understand how to think of the approach to tackle the problem.

The first intuition which comes in our mind to sort the each pair according to travel cost to city A then send first N/2 person to city A and rest to city B.

Yes you can think of this approach but my friend the second example is already sorted according to travel cost to city A.

Our previous approach will not give you the minimum cost. Just think of another approach. Before that let me ask you one question,

#### What do you actually want to do..??

You want to send that employee to city A, where sending the same employee to city B is costlier.

But in the above example, for every employee, travelling to city A is cheaper, so in this situation, you want to send those employees to city B were travelling to city B is not much costlier than travelling city A. I mean where difference between both the prices is minimum.

Well mate! Are you thinking this approach, so let me tell you that you are thinking in the right direction. Just write the code accordingly.

### Greedy Solution

So, the approach we discussed above is actually a greedy approach. We are greedily trying to manipulate the constraints so that it can minimise our overall cost.

So, I think now its our time to discuss the solution. The approach to its solution is similar to what we have discussed.

As we know if the difference of both the travel cost (A – B) is too high then we will send that employee to city A and if difference is low, we will send that employee to city B. This is what we have seen before.

Let’s see the code for better understanding,

``````static bool cmp(vector<int> &x, vector<int> &y)
{
return (x - x) > (y - y);
}

int twoCitySchedCost(vector<vector<int>>& costs) {

sort(costs.begin(),costs.end(),cmp);
int res = 0;

for(int i=0 ; i < costs.size() ; i++)
{
if(i < costs.size()/2)
{
res+=costs[i];
}
else
{
res+=costs[i];
}
}

return res;
}``````

Yes, in the above code we sort the vector of vector according to difference of travel cost (Travel cost to city A – Travel cost to city B) in descending order.

So now we will send first N/2 employees to city A whose (A – B) difference is more and rest N/2 to city B.

So now we are actually sending all the employees to both the cities at minimum cost which was asked in the problem.

Hope this Greedy Approach is clear to you guys. We will discuss one more question in this post. So don’t feel if you can’t solve this problem. Just learn how to approach the problem and that’s how you will improve.

Now let’s move to our next Question.

## Leetcode 122 : Best Time to Buy and Sell Stock II

Another Greedy algorithm problem Say you have an array price for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7

Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.

NOTE that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4

### Analysis of Problem Statement

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

Like for example, if the price of one share of the stock is Rs 5 on day 1 and its price is Rs 7 on day 2, so you can buy that share on day 1 and can sell it on day 2 to earn Rs 2 profit.

Here you are given an array list and you can buy and sell the share to earn profit. Now you have design the algorithm such that you can maximum profit.

Also you can one buy and sell one share at a time.

Let’s take an example,

Like in the above example, if you buy a share on day 0 (7) and sell it on day 1 (1), you have to suffer a loss. So it’s better not to buy share on day 0.

Now I think problem statement is clear, you have to buy and sell share to earn maximum profit.

Output of above example : 7

In the above example, you can buy stock on day 1 (1) and can sell it on day 2 (5) to earn a profit of 4 and similarly if you buy a stock on day 3 (3) and sell it on day 4 (6), you will earn a profit of 3 from that share. So maximum profit you can earn is (4 + 3 = 7).

Hope problem Statement is clear.

### Greedy Approach

If you observe carefully, above problem is an example of Greedy Algorithm where constraint is profit and you have to maximise it.

Now if you observe carefully, you can earn a profit only when the selling price is more than cost price.

So Greedily, we will find if price of share on current day is more than previous day. If yes, then we will count that share and we will store the profit.

We will move this way and at last we will get the maximum profit which we can earn.

Let’s see the code,

``````int maxProfit(vector<int>& prices) {

int s = 0;

for(int i = 1; i < prices.size(); i++)
{
if(prices[i] > prices[i-1])
{
s = s + prices[i] - prices[i-1];
}
}
return s;
}``````

It is a very simple code and I don’t any explanation is required to understand the code.

That’s all folks for today. We have discussed two basics Greedy Problems and also discussed the approach. We will solve more problems of higher difficulty later. So stay tuned. 