Determine if Two Events Have Conflict

#62 Most AskedEasy

Determine if Two Events Have Conflict #62 Most Asked

Easy

7 views

Topics:

ArraysStringsTwo Pointers

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

event1 = [startTime₁, endTime₁] and
event2 = [startTime₂, endTime₂].

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:

event1.length == event2.length == 2
event1[i].length == event2[i].length == 5
startTime₁ <= endTime₁
startTime₂ <= endTime₂
All the event times follow the HH:MM format.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the format of the input events? Specifically, how are the start and end times represented (e.g., strings, integers, date objects), and what is the unit of time (e.g., hours, minutes, seconds)?
Are the start and end times inclusive or exclusive? For example, if one event ends at 10:00 and another starts at 10:00, do they conflict?
What should I return if either of the input events are invalid, such as having a start time that is after the end time?
Are the event times always given in the same time zone, or should I account for potential differences in time zones?
Is it possible for the start and end times to be equal, and if so, how should that be interpreted (e.g., does an event of zero duration conflict with another event happening at that time)?

Brute Force Solution

Approach

The brute force approach to checking for event conflicts involves examining all possible relationships between the two events' time intervals. We consider every scenario of how the events might overlap or not overlap. If any overlap exists then there is a conflict.

Here's how the algorithm would work step-by-step:

Take the start and end times of the first event.
Take the start and end times of the second event.
Check if the first event starts before the second event ends, and the second event starts before the first event ends.
If both of those conditions are true, then the two events have some overlapping time and therefore conflict.
If either of those conditions are false, the events do not conflict because they do not share any time.

Code Implementation

def have_conflict(event_one_start_time, event_one_end_time,\
event_two_start_time, event_two_end_time):    # Check if the first event starts before the second event ends.
    if event_one_start_time <= event_two_end_time:

        #Check if the second event starts before the first event ends.
        if event_two_start_time <= event_one_end_time:

            #If both are true, there is a conflict
            return True

    #If the above conditions are false, there is no conflict.
    return False

Big(O) Analysis

Time Complexity

O(1) – The provided solution involves a fixed number of comparisons between the start and end times of the two events. The number of operations does not depend on the size of any input array or data structure. Therefore, the time complexity is constant, denoted as O(1).

Space Complexity

O(1) – The provided algorithm only uses a fixed number of variables to store the start and end times of the two events. It doesn't create any additional data structures like arrays, lists, or hash maps that would scale with the input size N (where N could represent the number of events or the size of the time intervals). Therefore, the auxiliary space used remains constant regardless of the input, resulting in O(1) space complexity.

Optimal Solution

Approach

To determine if two events conflict, we can check if they overlap in time. Instead of comparing every possible time within the events, we only need to check the start and end times of each event against the other.

Here's how the algorithm would work step-by-step:

Consider the two events, each with a start time and an end time.
Check if the first event's start time happens before the second event's end time.
Also, check if the second event's start time happens before the first event's end time.
If both of these checks are true, then the events overlap, and they have a conflict. If either of the checks are false, there is no conflict.

Code Implementation

def do_events_conflict(event_one_start, event_one_end, event_two_start, event_two_end):

    # Check if event one starts before event two ends
    if event_one_start < event_two_end:

        # Check if event two starts before event one ends
        if event_two_start < event_one_end:
            # If both checks are true, then the events overlap
            return True

    # If either check is false, there is no conflict
    return False

Big(O) Analysis

Time Complexity

O(1) – The solution involves checking a fixed number of comparisons between the start and end times of two events. Regardless of the actual time values or any external input size, only four comparisons are ever performed. Therefore, the runtime is constant and does not scale with any input size n, resulting in O(1) time complexity.

Space Complexity

O(1) – The provided logic only uses a few variables to store the start and end times of the two events for comparison. No dynamic data structures or arrays are used. Therefore, the space required does not scale with the input size (N, where N represents the total number of events, which is 2 in this case). The space complexity is constant.

Edge Cases

Case	How to Handle
Null or undefined input for either event time array	Throw an IllegalArgumentException or return false/error code indicating invalid input
Event 1 ends before it starts (startTime > endTime)	Return true immediately, because if start time is AFTER end time, there will always be overlap.
Event 2 ends before it starts (startTime > endTime)	Return true immediately, because if start time is AFTER end time, there will always be overlap.
Events are exactly adjacent, one ending at the exact moment the other starts (no overlap)	Ensure the comparison uses strict inequality (< and >) rather than less than or equal (<=) to avoid false positives
Event times are very large integers leading to potential overflow in calculations	Use long or BigInteger data types where appropriate, or check for overflow before returning a result
One event completely contains the other event	This scenario should be handled correctly by the general overlap check, but it's worth testing specifically
Start and end times for both events are exactly the same	The algorithm should correctly identify this as an overlapping scenario, returning true
All event times are zero or the same value (startTime == endTime for both events)	This should be considered as overlapping, and the function should return true

Null or undefined input for either event time array

How to Handle:

Throw an IllegalArgumentException or return false/error code indicating invalid input

Event 1 ends before it starts (startTime > endTime)

How to Handle:

Return true immediately, because if start time is AFTER end time, there will always be overlap.

Event 2 ends before it starts (startTime > endTime)

How to Handle:

Return true immediately, because if start time is AFTER end time, there will always be overlap.

Events are exactly adjacent, one ending at the exact moment the other starts (no overlap)

How to Handle:

Ensure the comparison uses strict inequality (< and >) rather than less than or equal (<=) to avoid false positives

Event times are very large integers leading to potential overflow in calculations

How to Handle:

Use long or BigInteger data types where appropriate, or check for overflow before returning a result

One event completely contains the other event

How to Handle:

This scenario should be handled correctly by the general overlap check, but it's worth testing specifically

Start and end times for both events are exactly the same

How to Handle:

The algorithm should correctly identify this as an overlapping scenario, returning true

All event times are zero or the same value (startTime == endTime for both events)

How to Handle:

This should be considered as overlapping, and the function should return true