Minimize Branch Merge Conflicts

AmazonHard

Several feature branches are merged into main, one whole branch after another. A branch is a list of commits, and a commit is the list of file paths it modifies. Paths are strings and may repeat inside a commit or across commits.

A commit conflicts when it modifies at least one path that some branch merged before its own branch also modifies. A commit never conflicts with a commit of its own branch. A commit counts once no matter how many of its paths clash.

Part 1: Smallest total over merge orders

Implement min_merge_conflicts(branches). The branches may be merged in any order. Return the smallest total number of conflicting commits over all merge orders.

With no branches, return 0.

Example 1
branches
[[["api/user.py"],["api/auth.py"]],[["api/auth.py"],["web/app.js"]],[["api/user.py","web/app.js"],["docs/readme.md"]]]
Output
2
Why: Merging branches 0, 1, 2 in that order costs 2: branch 1's first commit clashes on api/auth.py, and branch 2's first commit clashes once via api/user.py and web/app.js. Every order that merges branch 2 before branch 1 costs 3, so no order does better.

Constraints

0 <= len(branches) <= 15
1 <= len(branches[i]) <= 100
1 <= len(branches[i][j]) <= 10
A path may repeat within branches[i][j] or across commits of branches

Practice this question

Import your own questions

Paste a question you were asked and get a full problem: statement, tests and a checked solution.

Import a question