侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 675 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【差分】判断两个事件是否存在冲突【力扣第 316 场周赛】

GabrielxD
2022-10-23 / 0 评论 / 0 点赞 / 272 阅读 / 477 字
温馨提示:
本文最后更新于 2022-11-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

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


给你两个字符串数组 event1event2 ,表示发生在同一天的两个闭区间时间段事件,其中:

  • 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 格式给出

解题

方法一:差分

思路

把时间都转为以秒为单位然后做差分数组,如果根据差分还原时有元素超过了 1 就说明两事件存在冲突。

「差分数组基础」

代码

class Solution {
    public boolean haveConflict(String[] event1, String[] event2) {
        int[] diffs = new int[2000];
        ++diffs[Integer.parseInt(event1[0].substring(0, 2)) * 60 + Integer.parseInt(event1[0].substring(3))];
        --diffs[Integer.parseInt(event1[1].substring(0, 2)) * 60 + Integer.parseInt(event1[1].substring(3)) + 1];
        ++diffs[Integer.parseInt(event2[0].substring(0, 2)) * 60 + Integer.parseInt(event2[0].substring(3))];
        --diffs[Integer.parseInt(event2[1].substring(0, 2)) * 60 + Integer.parseInt(event2[1].substring(3)) + 1];
        int diff = 0;
        for (int d : diffs) {
            if ((diff += d) > 1) return true;
        }
        return false;
    }
}
0
博主关闭了所有页面的评论