what if sort intervals according to start time
ONEKING-jan challenge
where will you place the bombs for cases like
1 30
2 15
16 31
Yes, we can sort intervals according to start time. But then what is your approach? You have too merge them in such a manner which satisfies all the constraints. You may like to refer my solution here.
What I have done is, sorted all and merged. If the current interval’s start is greater then the end of interval at the top of stack, I push the current in the stack. (Because I need to put a separate bomb for this interval). Otherwise, I find the intersecting range of the two intervals(on the top and current one) and push that intersecting range in the stack. In the end, the size of stack will give me the least number of possible bombs required for destroying the whole kingdom.