0

Consider points on a line on the x-axis starting from 0 towards a positive direction.
There are N people standing on some points and there are M points that are dirty
I need to find out the minimum time required to clean all the dirty points.
At each second each person can move on point in any direction left or right or can stay
When a person comes to a dirty point the point gets cleaned

Example:
Consider person on [5,10] and dirty = [8] mean person is at point 5 and 10 and point 8
is the dirty point. The second person can go to point 8 and clean it. This will require 2 seconds

Consider [100,300] and dirty = [200,400] the first person could go from point 100 to point
200 and at the same time the second person could go from point 300 to 400
This will take 100 seconds.

Not sure how to approach it. Could one follow the greedy approach and simply move towards
the point that is closest. But then what if there are two points that are closest

dnaiel
  • 407
  • 7
  • 13
  • "*But then what if there are two points that are closest*" - Choose one randomly. – Turing85 Apr 24 '22 at 12:01
  • @Turing85 in the last example, 300 is also close to 200, but if I choose that, then the time taken to clean all dirty points will be more than 100. The tricky part is each person can move in any direction at the same time – dnaiel Apr 24 '22 at 12:06
  • I think you have kind of a travelling salesman with multiple salesmen problem, see https://stackoverflow.com/q/6239148/2846138 – cyberbrain Apr 24 '22 at 12:14

1 Answers1

0

General Statements

First we'll try to limit the search space by introducing some statements, convince yourself these are true.

  • It never makes sense for two persons to meet or pass each other. -> each point will be cleaned by either the person closest to the left or to the right -> at most 2^M cases to check
  • A person on an optimal path will change direction at most once. -> the time a person takes depending on the points it needs to clean can be defined as follows:
val s = start position
val l = min(points to clean)
val r = max(points to clean)
val dl = s - l
val dr = r - s
val time = when {
 dl <= 0 -> dr //points only to the right
 dr <= 0 -> dl //points only to the left
 else -> min(dl, dr) * 2 + max(dl, dr) //points on both sides, take shorter side twice
}

Brute Force Algorithm

val cases: List<Map<Person, List<Point>> = enumerate all 2^M cases where each point is either assigned to the closest person to the left or closest person to the right
val minTime = cases.minOf { case -> case.entries.maxOf { (person, points) -> time(person, points) } }

Time complexity of this algorithm is dominated by enumerating the cases in O(2^M).

An optimization would be to find all the left & right persons first.

F43nd1r
  • 7,690
  • 3
  • 24
  • 62