Last Updated: 3 Sep, 2025

Penguin Dance Pairing

Easy
Asked in company
Goldman Sachs

Problem statement

There are 'N' male and 'N' female penguins at a dance party. Each penguin has a specific height and a preference for a partner who is either strictly taller or strictly shorter.

The input represents this preference:

1) A positive height h means the penguin wants a partner with a height greater than h.
2) A negative height -h means the penguin wants a partner with a height less than h. The penguin's actual height is h.

Your task is to find the maximum number of male-female pairs that can be formed, where every penguin's height preference is satisfied. Each penguin can be in at most one pair.


Input Format:
The first line of input contains 'N', the number of male and female penguins.

The second line contains 'N' space-separated integers for the male penguins' heights and preferences.

The third line contains 'N' space-separated integers for the female penguins' heights and preferences.


Output Format:
Print a single integer representing the maximum number of dancing pairs.


Note:
A crucial insight is that pairings can only happen between two specific groups:
   1) Males who want a taller partner can only be paired with females who want a shorter partner.
   2) Males who want a shorter partner can only be paired with females who want a taller partner.
This splits the problem into two independent subproblems that can be solved greedily with a two-pointer approach after sorting.