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

【LetMeFly】2446.判断两个事件是否存在冲突

力扣题目链接：https://leetcode.cn/problems/determine-if-two-events-have-conflict/

给你两个字符串数组 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
解释：两个事件不存在交集。

 

提示：

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

方法一：（麻烦方法）让第一个开始时间不晚于第二个 + 字符串转整数

方法一是刚开始我想的方法。AC过后看了官解发现有更简单的方法。可以直接跳转到方法二。

不失一般性，我们让事件1的开始时间不晚于事件2。如果事件1的开始时间晚于事件2，就交换事件1和事件2。

这样，如果事件2的开始时间在事件1结束时间之后，就说明不冲突；反之则说明冲突。

怎么比较两个时间的先后呢？可以将时间（字符串）转为整数，代表这个时间是今天的第几分钟，之后就可以通过整数进行比较了。

• 时间复杂度$O(1)$
• 空间复杂度$O(1)$

AC代码

C++

inline int convertTime(string& s) {
    return (s[0] - '0') * 600 + (s[1] - '0') * 60 + (s[3] - '0') * 10 + (s[4] - '0');
}

class Solution {
public:
    bool haveConflict(vector<string>& event1, vector<string>& event2) {
        int t1s = convertTime(event1[0]), t1e = convertTime(event1[1]);  // t1 start, t1 end
        int t2s = convertTime(event2[0]), t2e = convertTime(event2[1]);
        if (t1s > t2s) {  // 令第一个开始时间不晚于第二个
            swap(t1s, t2s);
            swap(t1e, t2e);
        }
        return t2s <= t1e;
    }
};

Python

def convertTime(s: str) -> int:
    _0 = ord('0')
    return (ord(s[0]) - _0) * 600 + (ord(s[1]) - _0) * 60 + (ord(s[3]) - _0) * 10 + (ord(s[4]) - _0)

class Solution:
    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
        t1s, t1e = convertTime(event1[0]), convertTime(event1[1])
        t2s, t2e = convertTime(event2[0]), convertTime(event2[1])
        if t1s > t2s:
            t1s, t2s = t2s, t1s
            t1e, t2e = t2e, t1e
        return t2s <= t1e

方法二：直接开始比较

首先，不需要交换事件1和事件2的早晚。我们需要明白的是：事件1的开始时间晚于事件2的结束时间 或 事件2的开始时间晚于事件1的结束时间，则两事件不冲突。

其次，不需要将时间字符串转为整数，因为字符串之间可以直接比较。。。

• 时间复杂度$O(1)$
• 空间复杂度$O(1)$

AC代码

C++

class Solution {
public:
    bool haveConflict(vector<string>& event1, vector<string>& event2) {
        return !(event1[1] < event2[0] || event2[1] < event1[0]);
    }
};

Python

class Solution:
    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
        return not(event1[1] < event2[0] or event2[1] < event1[0])

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/130718458