It seems my approach to this problem is awkwardly wrong... I really need to start over and come up with a new way of thinking... but it's tough :\
because for now, instead of trying to do it correctly (which I'm not somehow) , I'm trying to patch in special case handling... argh
Greedily choose the next segment that covers the most additional points to the right of those already covered. You're choosing the maximum length segment instead, which as I pointed out in my test case, won't work.
Check input and AC output for thousands of problems on uDebug!
brianfry713 wrote:Greedily choose the next segment that covers the most additional points to the right of those already covered. You're choosing the maximum length segment instead, which as I pointed out in my test case, won't work.
I would like to know which case this code in Java does not work. I have tried several cases and no meeting which is failing. Can you help me telling which case fails?
Can some body help my. I don't know about Greedy . In 10020 problem, in the maximum test case - (Each test case in the input should contains an integer M(1<=M<=5000), followed by pairs "Li Ri"(|Li|, |Ri|<=50000, i<=100000), ) i = 100000, may I use Depth first search with Dynamic programing.
brainfry - Thank you so much for all of your sample IO. You have helped me so much over the past month or so since I started these problems. I really appreciate it.
Anyways, to the rest of the people who read this... the description does not say the input will be integers, BUT I used a greedy algorithm like everyone else ( with a few optimizations ) and only used int's and got AC.
Sort by the starting coordinate of each segment
Set shouldBeCovered = 0,
while(shouldBeCovered < M)
get the max covering length (segment.end - shouldBeCovered + 1) segment that segment.start <= shouldBeCovered
If segment found
add to the segments that are in the solution
update shouldBeCovered = segment.end
else
No solution can be found
got AC. The main thing about the problem is that you should output the answer as you have chosen , not at the order as they are in the input. If brianfry's input makes the correct output the code will produce an accepted result