Maximum coins possible with different x and y coordinates

Revision en1, by OneWhoKnocks, 2019-12-03 06:21:37

Problem Statement:

There are n Coins present in a cartesian plane. We have been given coordinates(x,y) of these coins. We can take home as much of these coins possible, given constraint that no 2 coins should have either x or y coordinates in common. Find the maximum number of coins we can take back home.

My Approach:

For a particular coin with x and y coordinates, i added 2 vertices(x and y) having an edge between them. So, i was able to convert this problem to a graph problem which will be to find minimum number of vertices to be removed so that each vertex in the graph has an edge with only one other vertex.

I wanted to discuss the possible approaches to solve this problem. Thanks.

Tags #graph, #dfs, #recursion, #geometry

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English OneWhoKnocks 2019-12-03 06:21:37 764 Initial revision (published)