Teaching Kids Programming – Determine if Two Events Have Conflict (Intersections of Two Intervals)

Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given two arrays of strings that represent two inclusive events that happened on the same day, event1 and event2, where:

event1 = [startTime1, endTime1] and
event2 = [startTime2, endTime2].
Event times are valid 24 hours format in the form of HH:MM.

A conflict happens when two events have some non-empty intersection (i.e., some moment is common to both events).

Return true if there is a conflict between two events. Otherwise, return false.
Example 1:
Input: event1 = [“01:15″,”02:00”], event2 = [“02:00″,”03:00”]
Output: true
Explanation: The two events intersect at time 2:00.

Example 2:
Input: event1 = [“01:00″,”02:00”], event2 = [“01:20″,”03:00”]
Output: true
Explanation: The two events intersect starting from 01:20 to 02:00.

Example 3:
Input: event1 = [“10:00″,”11:00”], event2 = [“14:00″,”15:00”]
Output: false
Explanation: The two events do not intersect.

Constraints:
evnet1.length == event2.length == 2.
event1[i].length == event2[i].length == 5
startTime1 <= endTime1
startTime2 <= endTime2
All the event times follow the HH:MM format.

Determine if Two Events Have Conflict (Intersections of Two Intervals)

It is easier to check the opposite case where two intervals not overlaping or two events not having conflicts. Then the opposite of that is two having conflicts or intersection.

1
2
3
4
5

class Solution:
    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
        a1, a2 = event1
        b1, b2 = event2
        return not (b2 < a1 or b1 > a2)

class Solution:
    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
        a1, a2 = event1
        b1, b2 = event2
        return not (b2 < a1 or b1 > a2)

Another condition for two events to conflict is the larger of the starting point is less or equal than the less of the ending point:

1
2
3
4
5

class Solution:
    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
        a1, a2 = event1
        b1, b2 = event2
        return max(a1, b1) <= min(a2, b2)

class Solution:
    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
        a1, a2 = event1
        b1, b2 = event2
        return max(a1, b1) <= min(a2, b2)

O(1) time and space.

–EOF (The Ultimate Computing & Technology Blog) —