Count The Number Of Players Who Need Training And Have Strictly Less Power And Endurance Than Any Other Player

Rhythm Jain
Last Updated: May 13, 2022

Introduction

In this article, we are going to solve a problem based on a greedy approach.

Let’s proceed deeper into the Problem statement and its solution approach.

Problem Statement

We are given a 2D array consisting of three components [power, endurance, id]. A player needs training if its power and endurance are strictly less than the power and the endurance of any other player. The task is to find the number of players who need training with their ids. 

Example:

INPUT:

{{1, 2, 1}, {2, 3, 2}, {3, 4, 3}}


OUTPUT:

2
1 2


Explanation:

Below are the players who need training

Player with id = 1, having power = 1 and endurance = 2 is strictly less than player with id = 3. 

Player with id = 2, having power = 2 and endurance = 3 is strictly less than player with id = 3.

Approach: Greedy Method

We can use Greedy Approach to solve the problem. 

Suppose we have two players X and Y. Player X needs training if there exists a Player Y such as the power of Player XPower of Player Y and endurance of Player Xendurance of the Player Y

We can sort the array on the basis of two parameters, Power and Endurance in non-decreasing order. That is first we will compare power, If power is the same then we will compare endurance and sort according to decreasing order of endurance.

In the C++ Sort function, we can custom sort using our own comparator function.

Algorithm

  • Write a custom comparison function that compares two entities, power and endurance such that power will be in increasing order and when power of two players are same then sort them according to endurance in decreasing order.
  • Sort the input array according to the comparison function mentioned above.
  • Iterate through the players[][] array from the right side, keeping account of the maximum previous endurance.
    • If any player is eligible for training, store its id.
    • If the current player's endurance is less than the previous maximum endurance value, increase the player count.
    • Otherwise, the maximum endurance value should be updated.
  • Return an array containing the ids of all players who require training.

Code

#include <iostream>
#include <bits/stdc++.h>
using namespace std;


vector<int> CountOfPlayers(vector<vector<int> >&players)
{
int count = 0;
int n = players.size();
sort(players.begin(), players.end(),[](vector<int>& v1, vector<int>& v2)
    {
       
             // If power value is equal
             // for both elements
             // Sort in descending order
             // according to endurance value
             if (v1[0] == v2[0])
                 return v2[1] < v1[1];
 
             else
                 return v1[0] < v2[0];
         });


// Keep track of maximum
// endurance value in right side
	int ma = 0;


	vector<int> res;


// Traverse the array players
	for (int i = n - 1; i >= 0; i--) {


		// If current endurance
		// value is smaller than
		// max then we will
		// increment the count
		int id = players[i][2];
		if (players[i][1] < ma) {

			// Adding player
			res.push_back(id);

			// Increase the count
			count++;
		}
		// Update max endurance value
		ma = max(ma, players[i][1]);
	}


	return res;
}


// Driver Code
int main()
{
	vector<vector<int> > players = {{1, 2, 1}, {2, 3, 2}, {3, 4, 3}, {3,3,4}};
	vector<int> ans = CountOfPlayers(players);


	cout << ans.size() << "\n";

	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] << " ";
	}


	return 0;
}

Output

2
2 1 

Complexity Analysis

Time Complexity: O(N*logN)

Because sorting takes O(NlogN) time for N items and here we are sorting players array with N items.

Space Complexity: O(1)

Some variables are used which use only O(1) constant space.

Frequently Asked Questions

  1. What is the time complexity of the STL sorting algorithm in C++?
    The common STL sorting algorithm in C++ in O(NlogN) in time complexity.
     
  2. What are the best-case and worst-case time complexity of Quick Sort?
    The best-case scenario is when the list is generated completely at random which is O(NlogN) time complexity.
    The worst-case scenario is when the array is already either sorted in ascending or descending order which is O(N2) time complexity.

Key Takeaways

In optimization problems, a greedy algorithm is a straightforward, intuitive solution. It tries to find the overall best solution to the problem, the algorithm takes the best decision at each phase.

If you wish to learn more about greedy algorithms, you can visit Greedy Algorithms in Array.

Although it is always suggested that solving the problem using a naive approach but observing the solution and problem carefully can yield great results. Observation is a great tool in developing the most efficient solutions and can improve our problem-solving skills.

Happy Coding!

Was this article helpful ?
0 upvotes