Minimize Branch Merge Conflicts
Asked at Amazon
AmazonReported by the problem's creator, not verified
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.
Examples
Example 1
Input: branches =
[[["api/user.py"],["api/auth.py"]],[["api/auth.py"],["web/app.js"]],[["api/user.py","web/app.js"],["docs/readme.md"]]]Output:
2Explanation: 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 viaapi/user.pyandweb/app.js. Every order that merges branch 2 before branch 1 costs 3, so no order does better.