Company Merger Problem

help
1

What would be the efficient approach to solve this problem :

Several car company exist in such a way that each company can control a large share of sales in different markets. You are required to perform a simulation that modifies the results after any mergers that happen between these companies.
Your task is to determine the minimum number of mergers that must be performed between the car companies to ensure that a market is controlled by no more than two separate companies.
INPUT n -> no of companies, m -> no of markets shared by each company.
next n line, where ith line contains m markets ID, controlled by company i.
Constraints:
1<=n<=5
1<=m<=3
1<=market_ID<10^5
Sample Input
2 2
1 2
2 3
Sample Output:
0

2 Likes
2

I believe a brute force recursive solution will work for constraints this small, for each recursive step, check if any market is owned by more than 2 companies.If this is not true, return 0 as total mergers required.Otherwise merge all 2 companies in current set of companies, and pass the newly formed (n-1) companies to next recursive step, and keep the minimum of all mergers.

1 Like