leetcode
leetcode 2101 ~ 2150
判断两个事件是否存在冲突

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

难度:

标签:

题目描述

代码结果

运行时间: 24 ms, 内存: 0.0 MB


/*
 * 思路:
 * 1. 使用流将时间转换为分钟数。
 * 2. 通过流处理检查时间段是否重叠。
 */
import java.util.stream.Stream;

public class Solution {
    public boolean haveConflict(String[] event1, String[] event2) {
        int[] times1 = Stream.of(event1).mapToInt(this::convertToMinutes).toArray();
        int[] times2 = Stream.of(event2).mapToInt(this::convertToMinutes).toArray();
        return times1[0] < times2[1] && times1[1] > times2[0];
    }

    private int convertToMinutes(String time) {
        String[] parts = time.split(":");
        return Integer.parseInt(parts[0]) * 60 + Integer.parseInt(parts[1]);
    }
}

解释

方法:

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

时间复杂度:

O(1)

空间复杂度:

O(1)

代码细节讲解

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

相关问题