This is a problem I was given back when I'm training for APIO Vietnam team selection.
"There are n factory that is planned to be built on a line, number from 1 to n. There are m restriction, each restriction has form uv, meaning that if both factory u and v is built, x u + 1 = x v. There are another p restriction, each restriction has form uv, meaning that if both factory u and v is built, x u ≤ x v. ( x i mean coordinate of factory i, if it's going to be built)
Your task is to choose a set of factories to build, and pick an appropriate coordinate for each factory, such that no restriction is violated, and the number of built factories is maximum."
I didn't understand the solution to this problem well back then. And now I'm trying to solve this again, but I can't think of any good idea. Can anyone give me a hint? Thanks in advance.