LeetCode 749. Contain Virus (TLE) – AlanShawn's Blog
I have obviously overestimated the complexity of the problem. I thought we need to choose a contaminated area to quarantine so that the world can be saved, but it is not the case. We only need to quarantine the most dangerous area each day, which resulted in overwhelmingly complicated design of the algorithm. I tried to use generalized algorithms without modification, but it gives me an TLE error. After profiling, I find out the the problem is in connected-component finding. We do not need to find a connected-component every time. In fact, we just need to run it once and keep track of the changes of the connected component. I do not want to modify my code to let it pass, because rather than a algorithm problem, it is more of a program design problem. I think I have devised a working algorithm, which is just not fast enough, due to a more sophisticated design and the capability of fulfilling multiple purposes.
Read full article from LeetCode 749. Contain Virus (TLE) – AlanShawn's Blog
No comments:
Post a Comment