如果我对问题的理解正确，那么这并不是您所链接论文中描述的NP问题的一个实例。这是我对问题的理解以及多项式时间解。
我们给定了一组实数范围，例如n：[A1，B1]，[A2，B2]，…，[An，Bn]，其中Ai <= Bi。
创建起点和终点的排序列表，并按数字顺序排列，以指示该点是起点还是终点。
在您的示例中，该值为：12 +，14 +，15 +，17 +，20 +，21-，22-，25-，27-，62 +，64 +，65-，70-，80-
将curOverlap和maxOverlap初始化为零。
遍历列表，为每个+增加curOverlap，为每个-减少。在每个增量上设置maxOverlap = max（curOverlap，maxOverlap）。
要继续例如： 缬氨酸，CUR，最大 12，1，1 14，2，2 15，3，3 17，4，4 20，5，5 21，4，5 22，3，5 25，2,5 27，1，5 62，2，5 64，3，5 65，2，5 70，1，5 80，0，5
最大重叠值为5。如果您想知道最大重叠发生在何处，也可以存储与最大关联的val。在此示例中，这将为您提供20。然后遍历初始范围并找到包含20个范围的5个范围很简单。
-edit-如果您有重复的值，请在每个值的负号之前对正号进行计数，以便包括在单个点处重叠的范围。
602392714
清零编程群