Example Input:

``````5 6
3 1 3 5
2 1 2
2 1 5
3 2 3 5
1 4
2 3 5
``````

Output: 3

Explanation:
you have 5 stamps to sell.
you have 6 buy offers. These want to buy the following Stamp IDs
1st: [1 3 5]
2nd: [1 2]
3rd: [1 5]
4th: [2 3 5]
5th: [4]
6th: [3 5]

You want to maximize the amount of accepted offers. Therefore accepting the offers 2, 5 and 6 is the best. This way you will sell the stamps [1 2 3 4 5]. (Note: you maximize the amount of accepted offers, not the amount of sold stamps)

More Testcases

Input:

``````6 6
3 1 2 3
3 2 3 4
3 4 5 6
2 3 4
2 2 6
2 1 5
``````

Output: 3
Input:

``````4 6
1 1
1 2
1 3
1 4
2 1 2
2 2 3
``````

Output: 4
Input:

``````5 6
2 1 2
2 2 3
2 3 4
2 4 5
2 1 2
2 2 3
``````

Output: 2

2 Likes

You have N unique stamps and there are total M buyers who want to buy these stamps. Each buyer wants to buy some certain stamps only. You have to choose to which buyers you should sell the stamps so that you have maximum number of buyers. One type of stamp can only be bought by only one buyer.
Note: You can choose a buyer if and only if you have all the stamps that he wants.
For eg:
If Buyer 1 wants to buy stamps A, B, C, E and buyer 2 wants to buy stamps B, D. Then you can sell the stamps to only one of them as they both want to have stamp B and you only have one stamp B.
Conclusion: If there are buyers who have a conflict in the stamps they want, you can only sell it to one of them.

2 Likes

yeah now I am understand but in last test case there is something wrong .

1 Like

Yes, the testcase will be -
5 6
2 1 2
2 2 3
2 3 4
2 4 5
2 1 2
2 2 3
OUTPUT: 2

thanks buddy !!!

1 Like