VISIBLEBOX - Decreasing Number of Visible Box
Shadowman loves to collect box but his roommates woogieman and itman don't like box and so shadowman wants to hide boxes as many as possible. A box can be kept hidden inside of another box if and only if the box in which it will be held is empty and the size of the box is at least twice as large as the size of the box.
Print the minimum number of box that can be shown.
The input set starts with single line integer T (1<=T<=50) the number of test cases. Then following T cases starts with an integer N (1<=N<=100000) denoting the number of box. The next line contains N space separated positive integer. i-th of them contains a numbers Ai(1<=Ai<=100000) size of the i-th box.
Output the the case number and the minimum number of box that can be shown.
Input: 2 4 1 2 4 8 4 1 3 4 5 Output: Case 1: 1 Case 2: 3
Admin Deepak Baghel:
Easy O(max(A(i))) solution :)
time limit too strict except c/c++Last edit: 2016-01-31 08:46:48
Is the given input sorted or not?
Last edit: 2015-12-31 07:43:17
Last edit: 2015-12-03 10:32:35
Few points to be noted: The input array given is not in sorted order. Do maintain a tag/index/map for a counter of each element.