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.

Table of Contents

**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][0]** and the cost of flying the **ith** person to city **B**is **cost[i][1]**.

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][0], costs[i][1]** <= 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[1] - x[0]) > (y[1] - y[0]);
}
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][0];
}
else
{
res+=costs[i][1];
}
}
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**.