Doubt in explaination -ONEKING

doubt
oneking

#1

What happens if there are many kingdoms within a bigger kingdom say [1,9],[1,4],[5,6],[7,9]?what will be the number of bombs required.

1 bomb or 3 bombs ?


#2

I think, that problem statement is clear:

A kingdom of the form [L, R] can be destroyed completely by placing a bomb at a point x on the real line if L
≤ x ≤ R.

so can you destroy [1, 4] and [5, 6] with one bomb?

Apply golden rule: Do not assume something not written in problem statement.


#3

But can’t we destroy all kingdoms with a single bomb by destroying 1st kingdom i.e. [1 to 9] ? And answer of above test case should be 1 .Am i wrong in getting the problem .


#4

i think the intervals which overlap at some point can be destroyed by 1 bomb but which do not overlap have to be destroyed with another bomb.


#5

But 1 to 9 kingdom will be overlapped by all other kingdoms so if we will destroy it all other kingdoms should be destroyed …


#6

Try out this simple thing.

  1. Draw a real line.
  2. Find the overlapping regions.

Gives you 3.


#7

ofcourse 3 bombs will be required


#8

I had similar doubt (except the examples).

Thanks you very much @betlista :diamonds::diamonds: for clearing it up, finally got AC :slight_smile: .

Thanks again.


#9

Why should it work that way? There’s nothing like that written in problem statement, those are separate kingdoms…


#10

Back to the basics. Tell me, where you will place the bomb…