时间戳

首页 > 解决方案 > 给定一个约会列表，找到所有有冲突的约会

python - 给定一个约会列表，找到所有有冲突的约会

问题描述

我有一个关于查找冲突约会的问题。

Appointments: [[4,5], [2,3], [3,6], [5,7], [7,8]]
Output: 
[4,5] and [3,6] conflict. 
[3,6] and [5,7] conflict.

我试图自己解决这个问题，但失败了。我做了一些谷歌，但是，我不确定答案是否正确。你介意用 Python 分享你的想法吗？我目前的想法是先对区间进行排序，但不确定下一步该做什么。谢谢你的帮助。

更新：
我用 O(n**2) 找出了低效的方法，并想用 O(nlogn) 寻找答案。谢谢。

这是一个测试用例，如果它比它慢，有助于拒绝您的解决方案O(nlgn)

n = 10
intervals = []
for i in range(n):
    intervals.append((i, n))
print(intervals)

标签： pythonalgorithmsortingintervals

解决方案

注意：项目之间的正确比较用于给出陈述的结果。至少有一个其他示例不会给出所述答案，尽管它们确实有很好的解释。

您需要先对约会进行排序。无需花费额外的费用将排序限制为开始时间，因为该算法仅取决于所有约会的开始时间在结束时间之前或结束时间；正如给出的那样。

conflicts通过将约会的结束时间与列表理解中下一个约会的开始时间进行比较来提取。

注意：项目之间的正确比较用于给出陈述的结果。至少有一个其他示例不会给出所述答案，尽管它们确实有很好的解释。

您需要先对约会进行排序。无需花费额外的费用将排序限制为开始时间，因为该算法仅取决于所有约会的开始时间在结束时间之前或结束时间；正如给出的那样。

通过比较约会的结束时间和列表理解中下一个约会的开始时间来提取冲突，直到它们不冲突。

a = [[4,5], [2,3], [3,6], [5,7], [7,8]]
a.sort() # No need to sort on only start time
conflicts = []
for i, this in enumerate(a):
    for next_ in a[i+1:]:
        if this[1] > next_[0]:  # this ends *after* next_ starts
            conflicts.append((this, next_))
        else:
            break  # Don't need to check any more

print(conflicts)    #  [([3, 6], [4, 5]), ([3, 6], [5, 7])]

时间安排

有一个算法效率的讨论，所以我想我会在这个和@wuerfelfreaks 算法上运行时间，（用轻微的模型来收集和返回所有冲突作为一个列表）：

修改后的代码

a = [[4,5], [2,3], [3,6], [5,7], [7,8]]

def conflicts_p1(a):
    "paddy3118's code as a function returning list of tuple pairs"
    a.sort()
    conflicts = []
    for i, this in enumerate(a):
        for next_ in a[i+1:]:
            if this[1] > next_[0]:  # this ends *after* next_ starts
                conflicts.append((this, next_))
            else:
                break  # Don't need to check any more
    return conflicts

def conflicts_w1(appointments):
    "@wuerfelfreak's answer returning a list of tuple pairs"
    appointments.sort(key= lambda x:x[0]) #appointments get sorted by start time.
    conflicts = []
    for i, a in enumerate(appointments):
        for i2 in range(i+1, len(appointments)):
            b = appointments[i2]
            if a[1] > b[0]: #if start of second appointment is before end of first appointment
                conflicts.append((a, b))
            else:
                break
    return conflicts

assert conflicts_p1(a) == conflicts_w1(a)

Ipython 计时

In [2]: # Paddy3118 timings

In [3]: %timeit conflicts_p1(a)
5.52 µs ± 38.6 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [4]: %timeit conflicts_p1(a)
5.42 µs ± 23.3 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [5]: %timeit conflicts_p1(a)
5.53 µs ± 438 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [6]: # wuerfelfreak timings

In [7]: %timeit conflicts_w1(a)
8.34 µs ± 141 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [8]: %timeit conflicts_w1(a)
7.95 µs ± 296 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [9]: %timeit conflicts_w1(a)
8.38 µs ± 371 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

In [10]:

概括

对于给定的示例，我的（Paddy3118 的）代码比 wuerfelfreak 的代码要快。

推荐阅读