algorithm - 最大相交间隔

Question

我有以下任务我得到了由3个间隔组成的N条规则。
A1 B1 C1 D1 E1 F1层
A2 B2 C2 D2 E2二层
A3 B3 C3 D3 E3 F3层
是的。
.
.
一个新的国家
每个规则由三个不同的间隔组成，[a，b][c，d][e，f]。
让我们考虑一个包含三个值x、y和z的输入。这个输入将满足一个规则，如果是< ＝d和e<= z <＝f。任务是找到通过任意输入可以满足的最大规则数的计数。
我试图用蛮力技术来解决这个问题这是o（n^2）解。我检查每一条规则和每一条规则是否相互交叉。我维护一个列表，在其中记录与当前规则相交的规则编号我使用这个记录输出最大的大小。但我用这种方法得到的答案是错误的。请帮我提供一个提示，告诉我可能做错了什么。
例子：
假设我们有5条规则：
规则1:39 40 43 55 28 42
规则2:6 15 36 43 12 56
规则3:38 57 3 15 17 36
规则4:3 15 36 60 21 52
规则5:24 45 23 34 27 39
在这里，我们可以计算出只有规则2和规则4可以通过任何输入同时满足因此，答案=2。

Answer 1

方法无效，因为当rule1与rule2相交，rule1与rule3相交时，这并不意味着rule2与rule3相交。
例子：

 Rule1:   [1,2] [3,4] [5,6]
 Rule2:   [1,1] [3,3] [5,5]
 Rule3:   [2,2] [4,4] [6,6]

在您的解决方案中，当您在外部循环中修复Rule1时，然后在嵌套循环中找到Rule2和Rule3，得到结果3，而正确答案是2。
我有一个可行的解决方案，但它不是很有效：O（K3*N），其中K来自规则区间定义域（K=max_interval_value-min_interval_value），N是规则数它还消耗O（k*n）内存。如果这个设置符合问题的时间和内存限制，我可以描述我的解决方案，否则，我宁愿不浪费时间。
更新：
好的，给你为了简单起见，我假设在规则中出现的最小数目是0，最大值是K.，因此只有k+ 1个可能的整数可以满足至少一个规则的间隔。
由于每个规则正好有三个间隔，因此必须创建三个与这些间隔相对应的数组。索引 i处的数组元素将包含一组规则，这些规则在相应的间隔中包含数字 i。每个数组的长度为k+1。
例如，如果我们有规则：

 A: [1,2][3,4][5,6]
 B: [1,1][2,2][6,6]
 C: [2,2][4,4][5,5]

然后第一个数组（对应于位置1处的间隔）将是：

 0:{}, 1:{A,B}, 2:{A,C}, 3:{}.... rest are empty sets

第二个数组对应于第二个位置的间隔：

 0:{}, 1:{}, 2:{B}, 3:{A}, 4:{A, C}, 5:{}, 6:{}

第三个数组是：

 ...all empty... 5: {A, C}, 6: {A, B}

现在如何填充这些数组从每个元素中的空集合开始。那你就要遵守所有的规则对于每个规则，您将遍历位于相应间隔内的所有值，并将当前规则添加到适当的集中。例如，对于第一个间隔的rule A，您需要遍历值1,2并将 A添加到索引1,2处的第一个数组中。这部分需要3*k*n个步骤（假设要设置的添加元素是o（1））
下一步要做的基本上是找出一个能满足大多数规则的输入。您需要三个嵌套循环，例如，第一个间隔 i，第二个间隔 j，第三个间隔 k。你需要迭代从0到K的所有可能值。对于i，j，K的每个组合，你需要相交于三个集合，每个集合取自相应的数组所以，回到这个例子，对于i=2，j=4，k=5，你需要将{a，c}与{a，c}与{a，c}相交，这将产生一组最大的规则。如果i=1，j=3，k=5，则{A，B}与{A}和{A，C}相交，只得到{A}所以，你迭代，计算交集，并找到最大的规则集。这部分的复杂性是O（k3*n），其中k3来自嵌套循环，n是集合相交的成本。
这就是全部。我对这个解决方案考虑不多，所以也许可以进一步优化。但至少是多项式。
更新
现在如何消除一个嵌套循环。
当您有一些 i和 j并且已经从前两个数组计算出组的交集时，您实际上得到了新任务。现在你有一组组，你需要找到这个集合的最大子集，它只满足一个剩余间隔（第三）。我建议将所有可能的值从0迭代到k，并为每个值维护由该值满足的组集。为此，必须以两种方式对组的初始子集进行排序，第一种是按第一个间隔的边界排序，第二种是按第二个间隔的边界排序。让我们调用第一个排序数组 add_order，第二个 remove_order。（稍后您将看到，为了简单起见，这些数组可以被队列替换）。
如果初始子集中有三个组：

 A: [..][..][2,4]
 B: [..][..][2,2]
 C: [..][..][1,3]

对于 add_order，它们将按以下顺序订购：c、a、b。

 C: [..][..][1,3]
 A: [..][..][2,4]
 B: [..][..][2,2]

b，c，a表示 remove_order：

 B: [..][..][2,2]
 C: [..][..][1,3]
 A: [..][..][2,4]

你的循环需要三个指针。第一个（ g_add）将指向（在数组中）要“添加”到维护集的组，第二个（ add_order）将指向（在数组中）要从集中删除的组。最后， g_remove将保持当前值（从0到k）。
回到示例中，您将从0到5迭代 remove_order（ k和 k最初指向对应数组的第一组）：

 k=0, g_add=C, g_remove=B, res={} // nothing to do
 k=1, g_add=C, g_remove=B, res={} // `g_add` is pointing on the group whose first boundary is less or equal to `k`, adding this group to set of current groups, and incrementing `g_add`
 k=1, g_add=A, g_remove=B, res={C} // moving on, incrementing `k`
 k=2, g_add=A, g_remove=B, res={C} // now A satisfies adding condition
 k=2, g_add=B, g_remove=B, res={C, A} // B satisfies adding condition too
 k=2, g_add=, g_remove=B, res={C, A, B} // incrementing k (note that at that point we have largest set)
 k=3, g_add=, g_remove=B, res={C, A, B} // B has second boundary less than k, removing
 k=3, g_add=, g_remove=C, res={C, A} // B has second boundary less than k, removing
 k=3, g_add=, g_remove=C, res={C, A} // k++
 k=4, g_add=, g_remove=C, res={C, A} // C is suitable for removing
 k=4, g_add=, g_remove=A, res={A} // k++
 k=5, g_add=, g_remove=A, res={A} // A is suitable for removing
 k=5, g_add=, g_remove=, res={} // we are done

如前所述，您可以将 g_add和 g_remove视为一个队列，它们的头将相应地被添加和移除候选者。
现在关于复杂性。迭代 remove_order和 add_order取o（k2）的所有对。现在对于每一个这样的对，你确实设置了交集o（n），你不需要对组进行排序，因为这可以在循环开始之前完成。然后需要迭代 i，添加和删除组。由于每个组只处理两次（当添加和移除）和 j从0到k迭代时，这个循环的复杂性将是O（n+k）。
所以对于整个算法，我们得到o（k2*（n+k）），考虑k<