The Problem

I have a set of sets of time intervals (hour, minute, day of the week). I want to select exactly one interval from each of set, and I want to minimize...

  • the number of pairwise intersections,
  • the total number of days,
  • the total time,
  • minus (the average start time), and
  • the average end time.

The number of intersections is always the most important, but the precedence of the other four is not known in advance. The number of sets is small (generally around 8), but the number of options can be pretty big (around 10), so trying all ~1E8 permutations is impossible.

What I've Tried

My current solution is to backtrack until I find a solution without intersections, giving up after a completely arbitrary number of iterations, and trying again with a higher number of allowed intersections. After repeating this process a few times, I select the best one.

This is probably really naive, so I came here hoping for a better approximation.

  • $\begingroup$ I know what it means by minimizing a single quantity, but what do you mean by minimizing several different ones? $\endgroup$ – Yuval Filmus Dec 6 '18 at 5:07
  • $\begingroup$ Oh sorry, I forgot to specify - each is only a tiebreaker for the last. $\endgroup$ – quadrupleslap Dec 6 '18 at 9:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.