Hi!
I've a problem with this problem, could anyone help me out with a hint? Anything is appreciated :)
Statement: There's a museum made up by N * N cells, forming a square. We should place N guards, so that in every column and row there's exactly 1 guard. Also the guards have their "preferences", so every of them have a rectangular area where he wants to be placed to guard. The problem is to give a distribution of the guards (N points) where everyone is in his preferred rectangle or state that there's no such distribution.
Here's the statement in hungarian language with a picture too: here.
Thank you for reading, have a nice day.
Try to divide problem into two independent problems.
I think that it is the same problem as here : http://main.edu.pl/en/archive/oi/3/wie
First solve problem for single dimension i.e. given n cells for guards to stand, each having preference of type (l,r) i.e. he will stand only in cells numbered from l to r, how will you place all in different cells. Once this problem is solved, solution for two dimensions is similar.
Thank you for your help, I've solved it finally :)
Would you kindly share the idea or the solution :D ?
First solve only for rows and then only for columns
Yes of course, here it is :)
Every rectangle of form (a;b;c;d) (where (a;b) stands for lower left corner and (c;d) stands for upper right corner) actually limits the place of guard on x-axis by (a;c), on y-axis by (b;d). So then we have a bunch of limits. First let's solve for x-axis, sort the limits by their right endpoint (if their right endpoint is equal, sort by their left). Second, let's mark all points unoccupied on the axis, then loop trough them: if we're at limit (p, q) then the x-coordinate of the guard with this limit is the leftmost point k, that is not occupied yet and p ≤ k ≤ q (if there's no such k then there's no solution). Next mark k occupied and continue the loop. This way we got x-coordinates of the guards, it can be done similarly for the y-coordinates.
Link to implementation: ideone
Thanks, it is clear now :D .