algoadvance

You need to determine if two events conflict with each other. Specifically, you are given the start and end times of two events and you need to check if these two events overlap.

The event times are given in the 24-hour format “HH:MM” and an event represented by its start time and end time will be in the following format:

You need to return True if the events overlap, and False otherwise.

Clarifying Questions

  1. What is the format of the input?
    • The input will be two lists of strings, each containing two elements representing the start and end times of the events, e.g., ["09:00", "10:30"].
  2. Should we consider the endpoints?
    • Yes. If one event’s end time is the same as another event’s start time, we do not consider it as a conflict.
  3. Will the start time always be before the end time for both events?
    • Yes. It is given that the start time is always strictly before the end time for both events.

Strategy

To determine if two events overlap, we can convert the start and end times to a comparable format (like minutes from midnight) and then check the conditions for overlap.

An overlap exists if the two events do not fall completely outside each other’s boundaries. Mathematically:

In other words, two events conflict if:

Let’s convert these conditions into a step-by-step algorithm:

  1. Parse the time strings into hours and minutes.
  2. Convert these into total minutes from midnight.
  3. Apply the overlap condition.

Code

def to_minutes(time_str):
    """Convert a time string HH:MM into the total number of minutes from midnight."""
    hours, minutes = map(int, time_str.split(':'))
    return hours * 60 + minutes

def haveConflict(event1, event2):
    """Determines if two events have a conflict."""
    start1, end1 = event1
    start2, end2 = event2
    
    start1_minutes = to_minutes(start1)
    end1_minutes = to_minutes(end1)
    start2_minutes = to_minutes(start2)
    end2_minutes = to_minutes(end2)
    
    # Check for overlap condition
    return start1_minutes < end2_minutes and start2_minutes < end1_minutes

# Example usage:
event1 = ["09:00", "10:30"]
event2 = ["10:00", "11:00"]
print(haveConflict(event1, event2))  # Expected output: True

event1 = ["09:00", "10:00"]
event2 = ["10:00", "11:00"]
print(haveConflict(event1, event2))  # Expected output: False

Time Complexity

The time complexity of this solution is O(1) because:

  1. Parsing and converting the time strings both take constant time.
  2. The comparison operations also take constant time.

This solution is optimal since it doesn’t depend on the size of input data (since the input size is fixed and small).

Try our interview co-pilot at AlgoAdvance.com