判断两个事件是否存在冲突

标签: 数组 字符串

难度: Easy

给你两个字符串数组 event1 和 event2 ，表示发生在同一天的两个闭区间时间段事件，其中：

  • event1 = [startTime1, endTime1] 且
  • event2 = [startTime2, endTime2]

事件的时间为有效的 24 小时制且按 HH:MM 格式给出。

当两个事件存在某个非空的交集时（即，某些时刻是两个事件都包含的），则认为出现 冲突 。

如果两个事件之间存在冲突，返回 true ；否则，返回 false 。

示例 1：

输入：event1 = ["01:15","02:00"], event2 = ["02:00","03:00"]
输出：true
解释：两个事件在 2:00 出现交集。

示例 2：

输入：event1 = ["01:00","02:00"], event2 = ["01:20","03:00"]
输出：true
解释：两个事件的交集从 01:20 开始，到 02:00 结束。

示例 3：

输入：event1 = ["10:00","11:00"], event2 = ["14:00","15:00"]
输出：false
解释：两个事件不存在交集。

提示：

  • event1.length == event2.length == 2.
  • event1[i].length == event2[i].length == 5
  • startTime1 <= endTime1
  • startTime2 <= endTime2
  • 所有事件的时间都按照 HH:MM 格式给出

Submission

运行时间: 24 ms

内存: 0.0 MB

class Solution:
    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
        temp=[event1, event2]
        temp.sort()
        if temp[0][1]>=temp[1][0]:
            return True
        return False

Explain

该题解的思路是先将两个事件按照开始时间排序，然后比较第一个事件的结束时间和第二个事件的开始时间。如果第一个事件的结束时间大于或等于第二个事件的开始时间，则说明两个事件存在交集，即存在冲突，返回True。否则，返回False。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
        temp=[event1, event2]  # 将两个事件放入一个列表中
        temp.sort()  # 对事件按照开始时间进行排序
        if temp[0][1]>=temp[1][0]:  # 比较第一个事件的结束时间和第二个事件的开始时间
            return True  # 存在冲突
        return False  # 不存在冲突

Explore

给定的方法确实只考虑了两个事件的冲突情况。对于多个事件的冲突检查，我们需要对算法进行修改，以便处理任意数量的事件。一个常见的方法是： 1. 将所有事件按照开始时间进行排序。 2. 依次遍历排序后的事件列表，比较当前事件的结束时间与下一个事件的开始时间。 3. 如果当前事件的结束时间大于或等于下一个事件的开始时间，那么就发现了冲突。 这种方法首先通过排序，确保我们可以只比较连续的事件，这样可以有效地检测出所有可能的冲突。这种方法的时间复杂度主要由排序决定，通常是O(n log n)，其中n是事件的数量。