Hi all, I was attempting to solve Lifeguards, and was using a different approach than the one in the official analysis. My test case fails for 3 test cases, and I would really appreciate some help.
My approach is similar to the naive solution, to consider all lifeguards one by one, and compute the new time cover. However, to fit the time constraints, I compute the time cover for the current removal in O(1) time.
For eg. consider [1, 4] [3, 7] [5, 9]. I can compute the time cover when the 2nd interval is removed as {Original Cover} - {7-3} + {Overlaps with neighbours}. Which gives me 8 - 4 + 1 + 2 = 7.
My code can be found here.
My solution fails on test cases 5, 6 and 9. It produces a Wrong Answer. The test cases can be found here.
On analyzing the test case 5, I noticed that it contains intervals that are very huge, so maybe there is some overflows I am missing?
I tried storing and computing everything in %(1e9+7), and I could get test case 5 to pass, but I’m having difficulty proving whether it is correct.
