(RankList for this Question)
You and your friends got admission to the same Engineering college. In the initial days, you and your friends were living in the same room which was quite big. But as the days passed your friends started fighting with each other for the room. Now all friends decided that they will live in separate rooms but it is not an easy task. Each friend has some desired room size but they know that in a hostel there may or may not be a room which is of the exact same size as they want.
So each of them also has the desired range from size-k to size+k to accept a room and in one room only one person will be living.
Can you tell the maximum number of friends that will get the room in their desired range?
1 ≤ T ≤ 1000
1 ≤ n,m ≤ 2⋅10^5
0 ≤ k ≤ 10^9
1 ≤ Size[i], RoomSize[i] ≤ 10^9
T (Test case)
N (Number of friends) M (Number of rooms available in the hostel) K (Range number)
Size[N] (The desired room size of each friend. If the desired size is X then he/she can accept a room whose size lies between (X-K) to (X+K) (Inclusive))
RoomSize[N] (Size of the free rooms which are available in the hostel)
Print the maximum number of friends who will get a room in the hostel
4 3 5
60 45 80 60
30 60 75
For i=0 (0th friend wants a room of size Size =60 but he/she can accept a room between size 60-5 to 60+5 which is 55 to 65 is the desired range. So he/she can get the room which is on position j=1 RoomSize=60. (Room allocated to one and this room cannot be used further).
For i=1 (No room available)
For i=2 (Room available which is RoomSize=75 because the desired range is 75 to 85) (Room allocated)
For i=3 (No room available because the room size which satisfies the range is already allocated)
Maximum number of room allocated is 2
Log In to solve the Question