problem statement
After reading the problem statement, I just figured out a greedy solution. After reading the queries I sort them from top to bottom and from left to right, then I iterate over queries and try to assign supports to the current person, if his left support is free then I give him his left support otherwise if his right support is free I give him his right support, if both of them are not free then it is impossible to assign supports to them so that every person has a support.
This problem has another special solution, Maximum Bipartite Matching, We can build a bipartite graph, one part places to seat, another part supports, the edge are obvious, then we run MBM, if we can match all of the seats so that each seat has a support then the answer is YES otherwise the answer is NO.
Time complexity of the second solution is not good enough to pass the time limit I think so.
After reading the problem statement, I just figured out a greedy solution. After reading the queries I sort them from top to bottom and from left to right, then I iterate over queries and try to assign supports to the current person, if his left support is free then I give him his left support otherwise if his right support is free I give him his right support, if both of them are not free then it is impossible to assign supports to them so that every person has a support.
This problem has another special solution, Maximum Bipartite Matching, We can build a bipartite graph, one part places to seat, another part supports, the edge are obvious, then we run MBM, if we can match all of the seats so that each seat has a support then the answer is YES otherwise the answer is NO.
Time complexity of the second solution is not good enough to pass the time limit I think so.
No comments:
Post a Comment