Penguin Dance Pairing

Easy

0/40

0 upvote

Asked in company

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.

Detailed explanation ( Input/output format, Notes, Images )

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.

Sample Input 1:

2
1600 1800
-1700 -1900

Sample Output 1:

Explanation for Sample 1:

- Male penguins: {wants taller than 1600}, {wants taller than 1800}.
- Female penguins: {wants shorter than 1700}, {wants shorter than 1900}.
- This is one subproblem. We sort both lists: M={1600, 1800}, F={1700, 1900}.
- Pair male 1600 with female 1700 (since 1700 > 1600). 1 pair formed.
- Pair male 1800 with female 1900 (since 1900 > 1800). 1 pair formed.
- Total pairs = 2.

Sample Input 2:

2
-1800 -2000
1700 1900

Sample Output 2:

Explanation for Sample 2:

- Males want shorter partners (heights 1800, 2000).
- Females want taller partners (heights 1700, 1900).
- No male has a height greater than any female, so no pairs can be formed.

Expected Time Complexity:

The expected time complexity is O(N log N).

Constraints:

1 <= N <= 100000
1500 <= abs(height) <= 2500

Time limit: 1 sec

Approaches (1)

Approach 1

Penguin Dance Pairing

Time Complexity

Space Complexity

(100% EXP penalty)

Penguin Dance Pairing

Console