Minimum Groups to Deactivate Transformers

Problem n transformers each belong to a group (groups[]). Deactivation is all-or-nothing per group. Find the minimum number of groups to deactivate so that at least ceil(n/2) transformers are deactivated.

Input / Output

• Input: int array groups (group id per transformer).
• Output: minimum group count.

Constraints

• n up to 10^5; O(n log n) expected.

Example

• groups = [1,1,1,2,2,3] (sizes 3,2,1), threshold ceil(6/2)=3 → 1 (deactivate group 1 alone).