NOTE: We have mentioned “in most of the scenarios” in the earlier point because in some cases, this approach doesn’t always produce correct results due to the nature of not reversing the decision made.
This is why we opt for Dynamic Programming strategy in such scenarios.
Problem  Score  Companies  Time  Status 

Bulbs  200 

22:50  
Highest Product  200 

29:14  
Largest Permutation  250 

39:23 
Problem  Score  Companies  Time  Status 

Meeting rooms  200 

46:54  
Distribute Candy  300 

63:53  
Seats  300 

71:31  
Assign Mice to Holes  300 

21:02  
Majority Element  400 

19:05  
Gas Station  700 

55:56 
Problem  Score  Companies  Time  Status 

Disjoint Intervals  200 

30:36 
A greedy algorithm makes the choice that appears best at that instance of time with the hope of finding the best possible result. In general, the greedy algorithm follows the below four steps:
Let us understand this by considering some examples.
Imagine you are a very busy person and you have lots of interesting things to be done within a short span of time T. You would want to do maximum of those interesting todo things in the short time you have.
You have a integer array A, where each element ai represents the time taken to complete a task. Your main task is now to compute the maximum number of things that can be done in the limited time T.
By carefully observing the problem, we can say that this problem requires nothing but a simple application of Greedy algorithm. Our natural greedy instinct says that in order to accomplish maximum tasks, we have to do the tasks that require minimum amount of time.
currentTime
and numberOfTasks
. In order to solve this problem, we follow the below steps:
currentTime
variable.numberOfTasks
by 1.currentTime
<= T.import java.util.*;
public class InterviewBit{
public static int maximiseTasks(int[] A, int T){
Arrays.sort(A);
int currentTime =0;
int numberOfTasks = 0;
for(int i = 0;i < A.length;i++)
{
currentTime+= A[i];
if(currentTime > T)
break;
numberOfTasks++;
}
return numberOfTasks;
}
public static void main(String[] args){
Scanner s = new Scanner(System.in);
int N = s.nextInt();
//Time limit
int T = s.nextInt();
//populate A array
int[] A = new int[N];
for(int i =0;i<N;i++){
A[i] = s.nextInt();
}
int result = InterviewBit.maximiseTasks(A,T);
System.out.println("Maximum number of tasks achievable: " + result);
}
}
Given weights and values of n
items and the flexibility that you are allowed to break items or choose fraction of the items. Your task is to put these items in a knapsack of capacity W
to get the maximum total value of the items in the knapsack.
Input:
Number of items, n = 3
int[] weights = { 10, 20, 30 };
int[] values = { 60, 100, 120 };
int capacity = 50;
Output:
Maximum Value Attainable  240
Considering items of weight 10 kg and 20 kg and 2/3 fraction of 30 kg.
Hence total price will be 60+100+(2/3)(120) = 240
The brute force approach that comes to our mind first is to try all possible subset with all different fraction and then choose the best out of it. This approach is really time consuming and the time complexities could be exponential.
The efficient approach that can be used is to use Greedy Approach.
value/weight
for each item and then sort the items on basis of this ratio.import java.util.Arrays;
import java.util.Comparator;
public class IBFractionalKnapsack
{
// function to get maximum value attainable
private static double getMaxValue(int[] weights, int[] val,
int capacity)
{
WeightValue[] weightValue = new WeightValue[weights.length];
// Populate with the values
for (int i = 0; i < weights.length; i++) {
weightValue[i] = new WeightValue(weights[i], val[i], i);
}
// sorting items by value/weight ratio;
Arrays.sort(weightValue, new Comparator() {
@Override
public int compare(WeightValue o1, WeightValue o2)
{
return o2.ratio.compareTo(o1.ratio);
}
});
double totalValue = 0d;
for (WeightValue i : weightValue) {
int curWeight = (int)i.weight;
int curValue = (int)i.value;
if (capacity  curWeight >= 0)
{
// this weight can be picked while
capacity = capacity  curWeight;
totalValue += curValue;
}
else
{
// item cant be picked whole
double fraction
= ((double)capacity / (double)curWeight);
totalValue += (curValue * fraction);
capacity
= (int)(capacity  (curWeight * fraction));
break;
}
}
return totalValue;
}
// Weight value class
static class WeightValue
{
Double ratio;
double weight, value;
// item value function
public WeightValue(int weight, int value)
{
this.weight = weight;
this.value = value;
ratio = new Double((double)value / (double)weight);
}
}
// Driver code
public static void main(String[] args)
{
int[] weights = { 10, 20, 30 };
int[] values = { 60, 100, 120 };
int capacity = 50;
double maxValue = getMaxValue(weights, values, capacity);
System.out.println("Maximum Value Attainable  "
+ maxValue);
}
}
The previous example of maximising number of tasks was quite simple. We could easily understand how greedy approach could be applied to solve the problem. Let us focus on a more complicated example which is the problem of task scheduling based on priorities of each work. Note that a work (or a job) requires one or more tasks for completion.
The problem statement states that we have the following information:
You need to determine in what order you should complete the tasks to get the most optimum result. What is the condition for the optimal scheduling of tasks? Can priority[i] can be applied to any job J or just to J[i]? Let us find answers to these questions in depth in the upcoming “Analysis” section
Let us start by analysing our inputs. We have J
as the number of jobs that has to be done today. T
as the list of time duration of each task and P
is the list of priorities assigned to each task.
J(i) = T[1] + T[2] + .... + T[i] where 1 <= i <= N
J(1) = T[1] = 1
J(2) = T[1] + T[2] = 1 + 2 = 3
J(3) = T[1] + T[2] + T[3] = 1 + 2 + 3 = 6
F = (P[1] * J(1)) + (P[2] * J(2)) + ...... + (P[N] * J(N))
P[j] = P[k] where 1 <= j, k <= N
but they take different time durations to complete, then in what order do can we schedule the jobs?T[j] = T[k] where 1 <= j, k <= N
, but those tasks have different priorities assigned, then in what order can we schedule the jobs?t
i.e T[i] = t where 1 <= i <= N
J(1) = T[1] = t
J(2) = T[1] + T[2] = 2 * t
J(3) = T[1] + T[2] + T[3] = 3 * t
J(4) = T[1] + T[2] + T[3] + T[4] = 4 * t
:
:
J(N) = N * t
p
. Then our minimised objective function becomes:
F = (P[1] * J(1)) + (P[2] * J(2)) + ...... + (P[N] * J(N))
F = (p * J(1)) + (p * J(2)) + ...... + (p * J(N)) //Since P[i] = p
F = p * (J(1) + J(2) + ...... + J(N))
(J(1) + J(2) + ...... + J(N))
, which is possible only if we start to work on the tasks that require the shortest completion time.In this case, the priorities and the completion times of each task are totally different. This is the most common scenario that usually occurs.
Consider the scenario where you have 2 or more tasks and the main rules of choosing tasks i.e we select the task that has higher priority and shorter completion time first. But what if this results in conflict? Assume that we have tasks where one of them has higher priority but longer completion time and the other one has least priority and shorter completion time? ( i.e. P[1] > P[2] and T[1] > T[2] ). Which task should be completed first?
We can think of aggregating the varying parameters (completion time and the task priority) into a single defining parameter so that based on this parameter, we can schedule the tasks in a optimal manner. Now what should this parameter be?
(P[i]  T[i])
(P[i] / T[i])
T = [7, 3]
and P = [5, 2]
(P[1]  T[1]) < (P[2]  T[2])
. Hence second task can be completed first. The objective function becomes:
F = (P[1] * J(1))+ (P[2] * J(2)) = (2 * 3) +(5 * (7+3)) = 56
(P[1] / T[1]) > (P[2] / T[2])
. Hence, the first task can be completed first. The objective function becomes:
F = (P[1] * J(1)) + (P[2] * J(2)) = (5 * 7) + (2 * (7+3)) = 55
/**
* Let S = array of pairs to store the scores and their indices
* J = completion times of job
* F = objective function
* P = List of priorities
* T = time taken of task
* N = number of job
*/
ObjectiveFunctionF (P, T, N)
{
for i from 1 to N:
S[i] = ( P[i] / T[i], i )
Arrays.sort(S)
J = 0
F = 0
for i ranging from 1 to N: // Greedy selection
J = J + T[S[i].second]
F = F + P[S[i].second]*J
return F
}
O(N)
time each and one sorting functionality which takes O(N * logN)
. Hence, O((2 * N) + (N*logN)) = O(N*logN)
.1. (P[i] / T[i])
is different.2. ( P[1] / T[1] ) > ( P[2] / T[2] ) > .... > ( P[N] / T[N] )
G = ( 1, 2, 3, ....., N )
. Since G is considered as non optimal and G is not equal to O, we can say that O must contain two consecutive jobs (i,j)
in such a way that i > j
. This is true as the only schedule that has the indices increase monotonically is G = ( 1, 2, 3, ...., N )
Therefore, O = ( 1, 2, ..., i, j, ... , N )
where i > j
.k
other than i
and j
i
and thenj
k
now there will be 2 cases:
k
lies on left of i
and j
in O, while swapping tasks i
and j
, there is no effect on the completion of task k
since J(k) = T[1] + T[2] + ..T[k]+.. + T[j] + T[i] + ..
k
lies on the right of i
and j
in O, after the swap, the completion time of k
is J(k) = T[1] + T[2] + .. + T[j] + T[i] + .. T[k]+..
, k
will again remain the same.i
, the completion time before swap was J(i) = T[1] + T[2] + ... + T[i]
and after swap is J(i) = T[1] + T[2] + ... + T[j] + T[i]
. As we can see, clearly, the completion time of i
went up by T[j]
and there by deduce that the completion time for j
goes down by T[i]
. Due to swap:
(P[i] * T[j])
(P[j] * T[i])
i > j
signifies (P[i] / T[i]) < (P[j] / T[j])
. Therefore, we have (P[i] * T[j]) < (P[j] * T[i])
which means that the Loss < Profit
. This signifies that the swap effect improves algorithm O further but this contradicts the initially assumed fact that O is already an optimal schedule. Hence, we can say that greedy approach gave us the optimal algorithm.Though greedy algorithms don’t provide correct solution in some cases, it is known that this algorithm works for the majority of problems. However, greedy algorithms are fast and efficient which is why we find it’s application in many other most commonly used algorithms such as:
The most basic purpose of greedy algorithm is optimisation which can be either minimisation or maximisation based on our problem statement requirements.