This article was published as a part of the Data Science Blogathon.
Introduction
This article will solve a famous interview question that the greedy approach can optimally solve. You can find the complete question here. I will teach everything from very basic, like explaining the algorithm, proof of concept, and time complexity, and then I will show you the complete code.
What is a Greedy Algorithm?
This approach solves the problem by selecting the best optimum possibility available. If your current option is not the best, then don’t worry. Your complete result will be optimal. In simpler terms, we can say that by selecting a local optimum, we can get a global optimum. An example of a Greedy Algorithm is Fractional Knapsack. You can read more about that problem here.
Below are some applications of the Greedy Algorithm
Algorithm
We used the Greedy technique to solve the problem in an optimized way. We store the Time (t), Deadline (d), and Id (p) of each professor in a 2d array as shown below.
arr = { {t1, d1, p1}, {t2, d2, p2}, ……………..{tn, dn, pn} } ………..(1)
[Where, p0=0, p1=1, ……….. pn=n ]
Further, we sort the array arr firstly w.r.t Time (t) and then sort the same array again w.r.t deadline(d), both in ascending order. The algorithm used for sorting is Quick Sort which works on the Divide and Conquers algorithm.
We have sorted the array two times because if the deadlines of two professors are the same, then the professor with less class time (ti) will be kept first in the array.
Now we initialize two integer variables,
currTime = 0 …………(2)
annoyance = 0 …………(3)
Variable named currTime stores the current Time (current Time always starts from zero), and variable annoyance will store the total annoyance. Then we start iterating through that array and add the Time (ti) taken by each professor to the variable currTime as shown in eq(4).
currTime += ti ………..(4)
And during the iteration, if we found that the deadline (di) of that particular professor is less than the current value of currTime, then we add the difference of currTime and deadline (di) in the total annoyance as shown in eq(5).
annoyance += max(0, currTime – di) ………..(5)
Then we print the total annoyance in the first line, and in the following line, we print all the values of pi’s by iterating to that 2d array. It gives the order of classes taken by the professors.
Proof of Concept
In the brute force approach, we must take every combination of exponential time complexity. But our suggested algorithm will work in O(N log N) Time.
Greedy Approach:
a) Starts from those which have a minimum deadline(di).
b) If two professors have the same deadline(di), then choose first who has less Time (ti)
c) Add the individual minimum annoyance to the total minimum annoyance.
Our algorithm is optimal and gives the minimum possible maximum annoyance and minimum total annoyance. As we see, the value of the variable currTime (which initially starts from zero) increases after each iteration as each professor completes their class. In our algorithm, we subtract the current value of the variable currTime from each professor’s deadline(di) and add that difference to the total annoyance.
Higher the value of currTime and lower the deadline(di) will increase the total annoyance. So we will first conduct the classes of those professors whose deadline(di) is minimum. It will minimise the annoyance, as the difference between currTime and deadline(di) also minimizes. Also, the value of currTime is in increasing order. Initially, its value is also less. That’s why this algorithm is optimal among the others. And our local optimum solution is equal to the global optimum solution.
Time Complexity
In our algorithm, we first sort the array and then traverse through that array to find the total annoyance. So the time complexity of our complete algorithm will depend on the complexity of the sorting algorithm. The complexity of traversing through the array is only O(n) but even the best case time complexity of Quick Sort is O(nlogn).
Time taken by Quick Sort can be written as,
T(n) = T(k) + T(n-k-1) + S(n) …………(6)
The first two terms are for two recursive calls. The last term is for the partition process. k is the number of elements which are smaller than a pivot.
Worst Case- The worst case occurs when the partition process always picks the greatest or smallest element as a pivot. Following is recurrence for the worst case.
T(n) = T(0) + T(n-1) + S(n)
which is equivalent to,
T(n) = T(n-1) + Q(n) ………….(7)
The solution to the above recurrence is Q(n2).
Best Case: The best case occurs when the partition process always picks the middle element as the pivot. The following is recurrence for the best chance.
T(n) = 2T(n/2) + S(n) …………..(8)
The solution to the above recurrence is Q(nlogn).
Average Case- On average, we expect a mix of “good” and “bad” splits. So the time complexity for this case is O(N log N).
Therefore, the time complexity of our algorithm is as follows,
Average Case- O(n) + O(N log N) = O(nlogn)
Worst Case- O(n) + O(n2) = O(n2)
Best Case- O(n) + O(nlogn) = O(nlogn)
Although the worst-case time complexity of our algorithm is O(n2), Quicksort can be implemented in different ways by changing the choice of a pivot so that the worst case rarely occurs for a given type of data.
Code
Below is the code for the above problem. It is written in the C programming language. C language is chosen because it allows us to write every function independently. For ex-, you will see in the below code that we have implemented our max(), and swap() functions for finding the maximum element and for swapping two parts, respectively. But in programming languages like Python and C++, you will get inbuilt functions for performing these functionalities.
Input Format:
Firstly, you have to give the total number of professors who want to take a class.
Then in the following line, enter two space-separated variables denoting the time taken and the deadline of the ith professor.
N
t1 d1
t2 d2
.
.
.
tn dn
#include #include #define N 1
// Below function is used to find the maximum of the two elements.
int max(int a, int b)
{
if (a > b)
{
return a;
}
else
{
return b;
}
}
// Below function will swap the two integers. i.e. a becomes b, and b becomes a.
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
return;
}
// Below function is used to find the partition element for the quick sort.
int partition(int arr[][3], int p, int l, int h)
{
int pos = arr[h][p];
int i = l - 1;
for (int j = l; j < h; j++)
{
if (arr[j][p] <= pos)
{
i++;
swap(&arr[i][0], &arr[j][0]);
swap(&arr[i][1], &arr[j][1]);
swap(&arr[i][2], &arr[j][2]);
}
}
swap(&arr[i + 1][0], &arr[h][0]);
swap(&arr[i + 1][1], &arr[h][1]);
swap(&arr[i + 1][2], &arr[h][2]);
return (i + 1);
}
// This is the main function for performing the quick sort.
void quick_sort(int arr[][3], int p, int l, int h)
{
if (l < h)
{
// finding the pivot element
int r = partition(arr, p, l, h);
// perform the recursive call on the left side of the pivot element.
quick_sort(arr, p, l, r - 1);
// perform the recursive call on the right side of the pivot element.
quick_sort(arr, p, r + 1, h);
}
}
int main()
{
// Input the number of integers.
int n;
printf("Enter input:n");
scanf("%d", &n);
int arr[n][3];
for (int i = 0; i < n; i++)
{
scanf("%d %d", &arr[i][0], &arr[i][1]);
arr[i][2] = i + 1;
}
quick_sort(arr, 0, 0, n - 1);
quick_sort(arr, 1, 0, n - 1);
int annoyance = 0;
int currTime = 0;
for (int i = 0; i < n; i++)
{
currTime += arr[i][0];
int indiAnnoyance = max(0, currTime - arr[i][1]);
annoyance += indiAnnoyance;
}
printf("Total Annoyance: %dn", annoyance);
printf("Order: ");
for (int i = 0; i < n; i++)
{
if (i != n - 1)
{
printf("%d, ", arr[i][2]);
}
else
{
printf("%d", arr[i][2]);
}
}
}
Example:
INPUT
OUTPUT
Conclusion
In this article, we have discussed a famous interview question based on the Greedy Algorithm. As I also discussed above, the greedy algorithm is used for optimisation problems. But sometimes, that greedy method fails to find the optimal global solution. We will use a more advanced concept called Dynamic Programming for these problems. In simple terms, Dynamic Programming is used to optimise issues that follow the property of Overlapping Subproblems and Optimal Substructure. If a problem follows these two properties, then it is a guarantee that we can get a globally optimal solution using Dynamic Programming. I will define some famous problems of dynamic programming in further articles.
Key takeaways of today’s article:
1. Firstly, we understand the problem statement.
2. Then, we discussed the algorithm to solve that problem.
3. Thirdly, we prove that our algorithm is giving us the best optimal answer.
4. Then, we discussed the input and output format of the code.
5. Finally, we discussed the complete and optimised code to solve the problem.
This is all for today. In the further articles, I will discuss more such types in detail. If you liked that article, then please share it with others.
Thanks for reading, 🤩
The media shown in this article is not owned by Analytics Vidhya and is used at the Author’s discretion.
