algorithm - 在行中排列段而不重叠

Question

有一组带有{(a_i,b_i) with i = 1, ..., n}的段0 <= a_i < b_i <= 1，必须将其布置在N行[0,1]上，且不得重叠。

例如，如果一组可以由{(0.35,0.41), (0.40,0.43), (0.47,0.88)}和N >= 2组成，则可以排列这些段而不会重叠。使用N = 1是不可能的，因为第一段和第二段重叠。

在必须将段放置在哪一行上没有任何限制的情况下，一种可能的算法如下:根据段的起始位置a_i对段进行排序，然后将它们一个接一个地放置在N的一行上。如果无法将段a_i放置在任何行上而不与任何已放置的段重叠，则意味着没有解决方案。

如果某些线段在必须放置的线上有约束，该怎么办？例如，段(a_2,b_2)可以仅放在第三行，并将其写为(a_2,b_2;3)。

一种可能的情况如下:{(0.45,0.56;-), (0.48,0.67;-), (0.66,0.70;2), (0.68,0.71;-)}和N = 2。
如果将第一段放在第一行上，则第二段必须在第二行上，而第三段不能满足约束条件。相反，如果将第一段放在第二行上，则第二段在第一行上，第二段在第三行上满足约束，而最后一条在第一行上。

我尝试过的

尝试满足约束的每种组合。在最后一个示例中{1,2}x{1,2}x{2}x{1,2}在第一个没有重叠的地方之后，程序将返回组合，这是该问题的解决方案。当然可以，当然很慢。

画一条线[0,1]，标记至少是一个线段边界的点。建立一个由两个连续点组成的间隔的列表I。对于I的每个元素，获取覆盖它的各段的列表S。对于S'的每个子集S，build设置的A'等于它们允许使用的行号的并集。例如S' = {(0.5,0.6;1,2), (0.4,0.7;2)}，A' = {1, 2}。如果A'的基数小于S'的基数，则没有解决方案。不幸的是，情况并非总是如此。

根据其他段的约束，扫描点2.中的每个间隔，并删除段无法放置的行。例如，如果线段被约束在第2行上，则这是任何其他与其相交的线段的选择。继续扫描间隔列表，直到不再有减少的可能性为止。然后将1.中的基本算法与可能的组合子集结合使用。

绘制一个大小为A的方阵n(n为段数)。如果a_ij重叠，则等于1；如果不重叠，则等于0。根据段是否具有约束，仅允许对矩阵执行特定操作(如果交换两行，则必须交换相同的列，具有约束的段不能任意交换)。如果可以得到一个矩阵，矩阵中有许多对角线块<= N，它们就是单位矩阵，那么就可以找到解决方案。不知道这是否可行，也没有道理。

考虑I中定义的S，S'，A'和2.。如果A'的基数小于S'的基数，则中止(无解决方案)。如果A'的基数等于S'的基数，请从与A'的每个元素相交的段中删除S'的行号。

继续扫描I，直到无法再还原为止。 是真的吗，如果程序到现在还没有中止，那么剩下的所有可能的解决方案都可以解决这个问题？ (是，但不仅限于此)

例如，N = 3，S = {(0.5,0.6;1,2), (0.4,0.7;2), (0.5,0.6;1,2,3)}。子集之一是S' = {(0.5,0.6;1,2), (0.4,0.7;2)}，其子集具有A' = {1,2}。 S'的基数等于A'的基数，因此必须从每个不在{1,2}中的段允许的行中删除S'。一个获得S = {(0.5,0.6;1,2), (0.4,0.7;2), (0.5,0.6;3)}。对S' = {(0.4,0.7;2)}进行相同的操作，从第一段中删除2，然后获得S = {(0.5,0.6;1), (0.4,0.7;2), (0.5,0.6;3)}，这是(唯一可能的)解决方案。

反例:对于N = 2和{(0.5,0.6;-), (0.55,0.7;-), (0.65,0.8;-)}，并非{1,2}x{1,2}x{1,2}中的每个组合都是解决方案。原因与(真)解的对称性有关。如果在算法的每一次完整运行之后，将某段固定在其允许的一条直线上(从而破坏了对称性)并重新运行该算法，则可以为该提议的集合获得一种解决方案。

是否可以通过这种方式始终获得解决方案(如果存在)，或者程序在没有解决方案时中止运行？

如果5.是正确的，是否可以根据n段的解来计算n-1段的解？

观察(来自评论和来自我)

可以强制放宽某些段在某些特定行上的约束，因为完成解决方案后，您可以完全自由地对行重新编号，而无需更改单个行上的段是否重叠。因此，例如，如果假设两个网段在第5行上，那么这实际上意味着它们必须在同一行上；如果一个段应该位于第3行上，而另一个段应该位于第7行上，则这实际上意味着它们必须位于不同的行上。

如果任何点 x没有被任何线段覆盖，则可以将问题分为2个问题，即线 [0,x]和 [x,1]长，并且有两组不同的线段。因此，必须假定 [0,1]中的每个点都至少被一个段覆盖。

Answer 1

我认为这个问题可以翻译成Vertex Coloring:

让每个线段都是无向图中的一个顶点。如果相应的线段重叠，则两个顶点之间将有一条边。因此，我们需要为每个顶点(段)分配一种颜色(线号)，以使没有两个相邻的顶点具有相同的颜色(两个段不在同一条线上重叠)。

具有约束的变化可以描述为List Coloring。