Comfortable distance
This problem is not a very difficult one. But in my opinion, it is not easy.
When I first tried to solve this problem, the first and the last seat are quite troublesome. I also felt that occupancy of one seat would affect its neighbors, so it was difficult to use dynamic programming method.
I thought it over and finally found that this was just an relatively complicated combination problem. Several different situations needs to be handled. In each situation, it is relatively easy to find the number of ways to make all people seated following the rule.
My code's efficiency is not too bad. It takes less than 0.6 second to get the correct answer.
No comments:
Post a Comment