确定所有间隔是否重叠
Deciding if all intervals are overlapping
我在做一道n个人站在一条线上，每个人都知道自己的位置和速度的问题。我被要求找到让所有人去任何地方的最短时间。
基本上我正在做的是使用二进制搜索找到最短时间，并让每个人在该时间间隔内走最远的距离。如果所有区间重叠，就有一个大家可以去的地方。
我有这个问题的解决方案，但由于我的错误解决方案无法找到间隔，因此超出了时间限制。我目前的解决方案运行速度太慢，我希望得到更好的解决方案。
我的代码：
people = int(input())
peoplel = [list(map(int, input().split())) for _ in range(people)] # first item in people[i] is the position of each person, the second item is the speed of each person
def good(time):
return checkoverlap([[i[0] - time *i[1], i[0] + time * i[1]] for i in peoplel])
# first item,second item = the range of distance a person can go to
def checkoverlap(l):
for i in range(len(l) - 1):
seg1 = l[i]
for i1 in range(i + 1, len(l)):
seg2 = l[i1]
if seg2[0] <= seg1[0] <= seg2[1] or seg1[0] <= seg2[0] <= seg1[1]:
continue
elif seg2[0] <= seg1[1] <= seg2[1] or seg1[0] <= seg2[1] <= seg1[1]:
continue
return False
return True
（第一次提问，如有不妥请告知）
一个人确实是线性的
在我完成答案后不久，我发现了一种简化，它消除了排序的需要，从而使我们能够进一步降低查找是否所有间隔都重叠到 O(N)[ 的复杂性=60=].
如果我们查看初始排序后执行的步骤，我们会发现我们基本上是在检查
if max(lower_bounds) < min(upper_bounds):
return True
else:
return False
并且由于min和max都是线性的，不需要排序，我们可以通过以下方式简化算法：
- 创建一个下限数组 - 一次通过。
- 创建上限数组 - 一次。
- 进行我上面提到的比较 - 两次遍历新数组。
所有这些都可以一次完成以进一步优化（并防止一些不必要的内存分配），但是为了解释的目的，这更清楚。
由于正确性和时机的推理是在上一次迭代中完成的，这次我将跳过它并保留下面的部分，因为它很好地展示了优化背后的思考过程。
一种统治一切
免责声明： 此部分已被上面的部分废弃 time-wise。然而，由于它实际上让我找出了线性解决方案，所以我将其保留在这里。
正如标题所说，排序是一种相当直接的方法。它将需要一些不同的数据结构——我没有将每个间隔保持为 (min, max)，而是选择将每个间隔保持为 (min, index), (max, index)。
这使我可以按 min 和 max 值对它们进行排序。接下来是对排序数组的单次线性传递。我们还创建了一个 False 值的辅助数组。这些表示一开始所有区间都是闭合的。
现在是数组传递：
- 由于数组是排序的，我们首先遇到每个区间的
min。在这种情况下，我们增加 openInterval 计数器和间隔本身的 True 值。间隔现在打开 - 在我们关闭间隔之前，此人可以到达派对 - 我们在他（或她）的范围内。
- 我们沿着阵列走。只要我们打开间隔，一切都很好，如果我们设法打开所有间隔，我们就会有我们的聚会目的地，所有的社会距离都会崩溃。如果发生这种情况，我们 return True.
- 如果我们关闭任何间隔，我们就会发现我们的派对破坏者无法再继续下去了。 （或者我们可以讨论破坏派对的人是那些在有人已经离开时还懒得去的人）。我们return假.
最终的复杂度为 O(Nlog(N))，这是由初始排序引起的，因为传递本身在本质上是线性的。这比由“成对检查所有间隔”方法引起的原始 O(n^2) 要好得多。
代码：
import numpy as np
import cProfile, pstats, io
#random data for a speed test. Not that useful for checking the correctness though.
testSize = 10000
x = np.random.randint(0, 10000, testSize)
y = np.random.randint(1, 100, testSize)
peopleTest = [x for x in zip(x, y)]
#Just a basic example to help with the reasoning about the correctness
peoplel = [(1, 2), (3, 1), (8, 1)]
# first item in people[i] is the position of each person, the second item is the speed of each person
def checkIntervals(people, time):
a = [(x[0] - x[1] * time, idx) for idx, x in enumerate(people)]
b = [(x[0] + x[1] * time, idx) for idx, x in enumerate(people)]
checks = [False for x in range(len(people))]
openCount = 0
intervals = [x for x in sorted(a + b, key=lambda x: x[0])]
for i in intervals:
if not checks[i[1]]:
checks[i[1]] = True
openCount += 1
if openCount == len(people):
return True
else:
return False
print(intervals)
def good(time, people):
return checkoverlap([[i[0] - time * i[1], i[0] + time * i[1]] for i in people])
# first item,second item = the range of distance a person can go to
def checkoverlap(l):
for i in range(len(l) - 1):
seg1 = l[i]
for i1 in range(i + 1, len(l)):
seg2 = l[i1]
if seg2[0] <= seg1[0] <= seg2[1] or seg1[0] <= seg2[0] <= seg1[1]:
continue
elif seg2[0] <= seg1[1] <= seg2[1] or seg1[0] <= seg2[1] <= seg1[1]:
continue
return False
return True
pr = cProfile.Profile()
pr.enable()
print(checkIntervals(peopleTest, 10000))
print(good(10000, peopleTest))
pr.disable()
s = io.StringIO()
sortby = "cumulative"
ps = pstats.Stats(pr, stream=s).sort_stats(sortby)
ps.print_stats()
print(s.getvalue())
具有 10K 个随机值的传递测试数组的分析统计数据：
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.001 0.001 8.933 8.933 (good)
1 8.925 8.925 8.926 8.926 (checkoverlap)
1 0.003 0.003 0.023 0.023 (checkIntervals)
1 0.008 0.008 0.010 0.010 {built-in method builtins.sorted}
我在做一道n个人站在一条线上，每个人都知道自己的位置和速度的问题。我被要求找到让所有人去任何地方的最短时间。
基本上我正在做的是使用二进制搜索找到最短时间，并让每个人在该时间间隔内走最远的距离。如果所有区间重叠，就有一个大家可以去的地方。
我有这个问题的解决方案，但由于我的错误解决方案无法找到间隔，因此超出了时间限制。我目前的解决方案运行速度太慢，我希望得到更好的解决方案。
我的代码：
people = int(input())
peoplel = [list(map(int, input().split())) for _ in range(people)] # first item in people[i] is the position of each person, the second item is the speed of each person
def good(time):
return checkoverlap([[i[0] - time *i[1], i[0] + time * i[1]] for i in peoplel])
# first item,second item = the range of distance a person can go to
def checkoverlap(l):
for i in range(len(l) - 1):
seg1 = l[i]
for i1 in range(i + 1, len(l)):
seg2 = l[i1]
if seg2[0] <= seg1[0] <= seg2[1] or seg1[0] <= seg2[0] <= seg1[1]:
continue
elif seg2[0] <= seg1[1] <= seg2[1] or seg1[0] <= seg2[1] <= seg1[1]:
continue
return False
return True
（第一次提问，如有不妥请告知）
一个人确实是线性的
在我完成答案后不久，我发现了一种简化，它消除了排序的需要，从而使我们能够进一步降低查找是否所有间隔都重叠到 O(N)[ 的复杂性=60=].
如果我们查看初始排序后执行的步骤，我们会发现我们基本上是在检查
if max(lower_bounds) < min(upper_bounds):
return True
else:
return False
并且由于min和max都是线性的，不需要排序，我们可以通过以下方式简化算法：
- 创建一个下限数组 - 一次通过。
- 创建上限数组 - 一次。
- 进行我上面提到的比较 - 两次遍历新数组。
所有这些都可以一次完成以进一步优化（并防止一些不必要的内存分配），但是为了解释的目的，这更清楚。
由于正确性和时机的推理是在上一次迭代中完成的，这次我将跳过它并保留下面的部分，因为它很好地展示了优化背后的思考过程。
一种统治一切
免责声明： 此部分已被上面的部分废弃 time-wise。然而，由于它实际上让我找出了线性解决方案，所以我将其保留在这里。
正如标题所说，排序是一种相当直接的方法。它将需要一些不同的数据结构——我没有将每个间隔保持为 (min, max)，而是选择将每个间隔保持为 (min, index), (max, index)。
这使我可以按 min 和 max 值对它们进行排序。接下来是对排序数组的单次线性传递。我们还创建了一个 False 值的辅助数组。这些表示一开始所有区间都是闭合的。
现在是数组传递：
- 由于数组是排序的，我们首先遇到每个区间的
min。在这种情况下，我们增加openInterval计数器和间隔本身的True值。间隔现在打开 - 在我们关闭间隔之前，此人可以到达派对 - 我们在他（或她）的范围内。 - 我们沿着阵列走。只要我们打开间隔，一切都很好，如果我们设法打开所有间隔，我们就会有我们的聚会目的地，所有的社会距离都会崩溃。如果发生这种情况，我们 return True.
- 如果我们关闭任何间隔，我们就会发现我们的派对破坏者无法再继续下去了。 （或者我们可以讨论破坏派对的人是那些在有人已经离开时还懒得去的人）。我们return假.
最终的复杂度为 O(Nlog(N))，这是由初始排序引起的，因为传递本身在本质上是线性的。这比由“成对检查所有间隔”方法引起的原始 O(n^2) 要好得多。
代码：
import numpy as np
import cProfile, pstats, io
#random data for a speed test. Not that useful for checking the correctness though.
testSize = 10000
x = np.random.randint(0, 10000, testSize)
y = np.random.randint(1, 100, testSize)
peopleTest = [x for x in zip(x, y)]
#Just a basic example to help with the reasoning about the correctness
peoplel = [(1, 2), (3, 1), (8, 1)]
# first item in people[i] is the position of each person, the second item is the speed of each person
def checkIntervals(people, time):
a = [(x[0] - x[1] * time, idx) for idx, x in enumerate(people)]
b = [(x[0] + x[1] * time, idx) for idx, x in enumerate(people)]
checks = [False for x in range(len(people))]
openCount = 0
intervals = [x for x in sorted(a + b, key=lambda x: x[0])]
for i in intervals:
if not checks[i[1]]:
checks[i[1]] = True
openCount += 1
if openCount == len(people):
return True
else:
return False
print(intervals)
def good(time, people):
return checkoverlap([[i[0] - time * i[1], i[0] + time * i[1]] for i in people])
# first item,second item = the range of distance a person can go to
def checkoverlap(l):
for i in range(len(l) - 1):
seg1 = l[i]
for i1 in range(i + 1, len(l)):
seg2 = l[i1]
if seg2[0] <= seg1[0] <= seg2[1] or seg1[0] <= seg2[0] <= seg1[1]:
continue
elif seg2[0] <= seg1[1] <= seg2[1] or seg1[0] <= seg2[1] <= seg1[1]:
continue
return False
return True
pr = cProfile.Profile()
pr.enable()
print(checkIntervals(peopleTest, 10000))
print(good(10000, peopleTest))
pr.disable()
s = io.StringIO()
sortby = "cumulative"
ps = pstats.Stats(pr, stream=s).sort_stats(sortby)
ps.print_stats()
print(s.getvalue())
具有 10K 个随机值的传递测试数组的分析统计数据：
ncalls tottime percall cumtime percall filename:lineno(function)
1 0.001 0.001 8.933 8.933 (good)
1 8.925 8.925 8.926 8.926 (checkoverlap)
1 0.003 0.003 0.023 0.023 (checkIntervals)
1 0.008 0.008 0.010 0.010 {built-in method builtins.sorted}