Weighted Matching Greedy

Problem

Build a maximal weighted matching greedily: sort edges by decreasing weight, breaking ties by endpoint pair, and take each edge whose endpoints are still free.

edges is a list of [u, v, w] triples. Return [total_weight, pairs] where pairs are the chosen edges sorted.

Hint

Greedy matching is a 1/2 approximation for maximum weight matching.

Test cases

case 1

in: [4,[[0,1,5],[1,2,3],[2,3,4]]]

expected: [9,[[0,1],[2,3]]]

case 2

in: [3,[[0,1,2],[1,2,3],[0,2,1]]]

expected: [3,[[1,2]]]

case 3

in: [4,[]]

expected: [0,[]]

case 4

in: [2,[[0,1,7]]]

expected: [7,[[0,1]]]

Starter codePython

def weighted_matching_greedy(n, edges):
    # Your code here
    pass

4 test cases · run your code against them in the editor