# 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) {

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.

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.