A community choir director is preparing rehearsal rooms for the day before a concert. Every singer arrives already labeled with a voice-part code (a positive integer), and singers who share the same code are indistinguishable for scheduling purposes. The director must place every singer into exactly one rehearsal room so that: a room only ever holds singers who share one common voice-part code; no two different voice-part codes are ever placed in the same room (though a single code's singers may be spread across several rooms); and, because the venue's walls are thin, any two rooms that end up used that day must not differ in headcount by more than one singer. Subject to these rules, find the minimum number of rooms the director must open.
Line 1: an integer n — the number of singers. Line 2: n space-separated integers v_1 ... v_n — the voice-part code of each singer.
Print a single integer: the minimum number of rooms needed.
Example 1
Input
5 7 7 7 9 9
Expected
2
Explanation
Voice-part 7 has 3 singers and voice-part 9 has 2 singers. Using a maximum room size of 3, code 7 fits in a single room of size 3 and code 9 fits in a single room of size 2 (sizes 3 and 2 differ by only 1). That is 1 + 1 = 2 rooms, and fewer than 2 is impossible since the two codes can never share a room. Output: 2.
Example 2
Input
6 5 5 5 8 3 3
Expected
4
Explanation
Code 5 has 3 singers, code 8 has 1 singer, code 3 has 2 singers. Trying a maximum room size of 3 fails because the lone singer with code 8 would need a room of size at least 2 to stay within 1 of a size-3 room, which is impossible for a single singer. Using a maximum room size of 2 instead: code 5's 3 singers split into rooms of size 2 and 1 (2 rooms), code 8's 1 singer takes 1 room of size 1, and code 3's 2 singers take 1 room of size 2. All room sizes used are 1 or 2, differing by at most 1. Total rooms = 2 + 1 + 1 = 4, which is optimal. Output: 4.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →