Arrange the Students

Easy
0/40
Average time to solve is 10m
profile
Contributed by
6 upvotes

Problem statement

There are ‘N’ students each having some amount of blue and black pens (including 0). All you have to do is to arrange them in such a way that students having fewer pens always come before the students having the greater number of pens. If two or more students having the same total number of pens then the one having more blue pens will come first.

For Example : 
‘STUDENTS’ = [[2, 3], [5, 1], [1, 2], [4, 1]]
‘ANS’ = [[1, 2], [4, 1], [2, 3], [5, 1]]

Here, STUDENTS[i][0] and STUDENTS[i][1] represent the blue and black pens student ‘i’ have, respectively.
‘STUDENTS’ in terms of the total number of pens students have = [[5], [6], [3], [5]]
Arrange according to the requirement = [[3], [5], [5], [7]]. The fourth student will come before the first student as he has more blue pens.
Therefore, the final answer is [[1, 2], [4, 1], [2, 3], [5, 1]].
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case has an integer ‘N’ representing the size of ‘STUDENTS’.

The next ‘N’ lines have two single space-separated integers ‘BLUE’ and ‘BLACK’ which represent the blue and black pens ‘i-th’ student has, respectively.
Output Format : 
For each test case, print ‘N’ lines each having two integers separated by a single space representing the blue and black pens that the ‘i-th’ student has, under the condition given in the description.
Note : 
You don't need to print the output, it has already been taken care of. Just implement the given function.
Constraints : 
1 <= T <= 5
1 <= N <= 10^5
0 <= BLUE, BLACK <= 10^8

Time Limit: 1 sec
Sample Input 1 :
1
4
2 3
5 1
1 2
4 1
Sample Output 1 :
1 2
4 1
2 3
5 1
Explanation For Sample Input 1 :
For the first test case, the explanation is given in the description.
Sample Input 2 :
2
2
1 1
1 1
1
10 0
Sample Output 2 :
1 1
1 1
10 0
Explanation For Sample Input 2 :
In the first test case, there are two students with the same number of the total as well as blue pens, so we can place any student before any other.

In the second test case, there is a single student and so only one arrangement is possible.
Hint

Can you think of finding the solution after sorting the ‘STUDENTS’ with respect to the total number of pens?

Approaches (1)
Sorting

The basic idea is to sort the complete array on the basis of the total number of pens a student has. Please note that if two or more students having the same number of total pens then we are looking for the number of blue pens they have. Therefore, the comparator used to sort the array plays the most crucial role here.
 

Declaration of the ‘CMP’ (comparator) function:

bool cmp(vector<int> student1, vector<int> student2){ }

Where ‘student1’ and ‘student2’ are two students.

 

The steps are as follows:
 

  • Steps for the ‘CMP’ function.
    • Check if the total number of pens ‘STUDENT1’ has is equal to the total number of pens ‘STUDENT2’ has.
    • If the above step results true then:
      • Return true if ‘STUDENT1’ has more blue pens than ‘STUDENT2’.
      • Else, return false.
    • Return true if ‘STUDENT1’ has more pens than ‘STUDENT2’.
    • Else, return false.
  • For the given function:
    • Sort the ‘STUDENTS’ using comparator function ‘CMP’.
    • Return ‘STUDENTS’.
Time Complexity

O(N*log(N)), Where ‘N’ is the total length of the array ‘STUDENTS’.

 

Since we are sorting the array that takes O(N*log(N)) time and so, the overall time complexity will be O(N*log(N)).

Space Complexity

O(N), Where ‘N’ is the total length of the array ‘STUDENTS’.
 

Since we are sorting the given array that takes an average of O(N) space and so, the overall space complexity will be O(N).

Code Solution
(100% EXP penalty)
Arrange the Students
Full screen
Console