for an experienced programmer, it shouldn’t take more than 2-3 hours.
Los Angeles Department of Water and Power (LADWP) maintains an infrastructure of electric power poles in the city with some power lines connecting these poles, where lines[i] = [a, b] indicates that there is a bi-directional (un-directed) line between pole a and pole b. In other words, in a Graph data structure, these poles represents nodes whereas the bi-directional lines connecting them are edges.
The coverage of any PAIR OF POLES is defined as the total number of directly connected electric lines to either pole. Let’s say we have 4 electric poles (0, 1, 2 and 3) connecting to each other via lines = [[1, 2], [1, 3], [0, 1], [0, 3]]
Given the existing power lines, the pair of poles 0 and 1 has a total coverage of 4, as represented by the blue edges above. In the same power line infrastructure, the pair of poles 0 and 2 has a total coverage of 3 (as represented by the blue edges below):
So on and so forth. You will go through all of the possible pair permutation in the infrastructure to find their coverage.
Write a solution method that returns the MAXIMUM coverage of the given power line infrastructure as represented by lines, and k number of electric power poles.
0 comments