Given a set of intervals \$\mathcal{I} = \{I_1, \ldots, I_m\}\$, where each interval \$I_j\$ is represented by its bounds \$(a_j, b_j)\$, find a partition \$\mathcal{T}\$ of \$\mathcal{I}\$ of minimal cardinality such that for each set \$T_i \in \mathcal{T}\$ it holds \$\bigcap T_i \ne \emptyset\$. In other words, find a partition of minimal cardinality where all the intervals inserted in the same set have a common element.
Elements \$\{a_j, b_j\}\$ can be integers, floats, chars, strings, or any other data type that has a total order and at least \$16\$ elements * (boolean is not admissible). Your solution must support at least one such data type of your choice.
*: why \$16\$ and not any other number? It's an arbitrary limit, I want to give freedom to use any strange data type, but I do not want loopholish solutions.
You can either output:
- partition \$\mathcal{T} = \{T_1, \ldots, T_k\}\$, or alternatively
- a set of numbers \$S = \{s_1, \ldots, s_k \}\$ such that \$s_i \in \bigcap T_i\$ for each \$i\$.
Testcases
input output (format 1) output (format 2)
{}: [], [],
{(0, 1)}: [{(0, 1)}], [0],
{(0, 1), (2, 3)}: [{(0, 1)}, {(2, 3)}], [0, 2],
{(1, 2), (0, 3)}: [{(1, 2), (0, 3)}], [1],
{(0, 2), (1, 3)}: [{(0, 2), (1, 3)}], [1],
{(1, 2), (3, 4), (0, 5)}: [{(1, 2), (0, 5)}, {(3, 4)}], [1, 3],
{(0, 1), (4, 5), (2, 3)}: [{(0, 1)}, {(2, 3)}, {(4, 5)}], [0, 2, 4],
{(4, 5), (1, 2), (0, 3)}: [{(1, 2), (0, 3)}, {(4, 5)}], [1, 4],
{(0, 1), (2, 5), (3, 4)}: [{(0, 1)}, {(2, 5), (3, 4)}], [0, 3],
{(0, 2), (3, 5), (1, 4)}: [{(0, 2), (1, 4)}, {(3, 5)}], [1, 3],
Rules
- you can use any reasonable I/O format, for example:
- the input can be a list/set of tuples, or two lists;
- in case 1., the output can be a list/set of lists/sets of intervals; each interval can be represented as a tuple, or the index of its position in the input;
- in case 2., the output can be a list/set of numbers;
- you can take the cardinality \$m\$ of the input set as an additional input;
- the input set \$\mathcal{I}\$ may be empty (in this case you have to output an empty list/set);
- you can assume each interval is not empty nor degenerate, i.e. \$a_j < b_j\$;
- you can assume intervals are left-closed or left-open, and if they are right-closed or right-open, as long as it's consistent for all intervals;
- you cannot assume the intervals in the input are sorted according to any particular criteria.
This is codegolf, so the shortest code wins. Bonus \$-i\$ bytes if your solution works in less than exponential time.
Tips
- I think using closed intervals is the easiest way. I would have put it as a rule, but I prefer to leave freedom.
-
by lexicographically sorting the intervals, a minimal solution can be computed using a greedy algorithm.
