LeetCode 2446 - Determine if Two Events Have Conflict

LeetCode Problem 2446

Difficulty: 🟢 Easy
Topics: Array, String

Solution

Problem Understanding

The problem asks us to determine if two events on the same day overlap in time. Each event is given as a pair of strings in HH:MM format representing the start and end times. The output should be a boolean: true if there is any overlap between the two events, and false otherwise.

The input guarantees that the start time is always less than or equal to the end time for each event, and that the times are properly formatted, which simplifies validation. Edge cases to watch out for include events that touch exactly at their endpoints, such as ["01:00","02:00"] and ["02:00","03:00"], which should count as overlapping because the problem defines the events as inclusive. Another edge case is when one event is entirely contained within another.

The constraints are minimal - only two events of fixed length arrays - so efficiency is not a primary concern. The challenge lies in correctly comparing the times.

Approaches

A brute-force approach would involve generating all the minutes covered by each event and checking for any intersection. While correct, this approach is unnecessarily complex given the small input size. It would require parsing each time string to minutes and then iterating through possibly up to 1440 minutes for a full day. This works but is overkill.

The optimal approach is based on a simple observation: two intervals [start1, end1] and [start2, end2] overlap if and only if start1 <= end2 and start2 <= end1. This works because if one event starts after the other ends, there is no intersection, and in all other cases, there is. This approach avoids unnecessary iteration and directly compares the time boundaries.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(1)	O(1)	Convert times to minutes and iterate to find overlap; unnecessary for two events
Optimal	O(1)	O(1)	Compare start and end times directly using string comparison or minutes conversion

Algorithm Walkthrough

1. Extract the start and end times for both events.
2. Compare the start time of the first event with the end time of the second event.
3. Compare the start time of the second event with the end time of the first event.
4. If both conditions start1 <= end2 and start2 <= end1 hold, return true.
5. Otherwise, return false.

Why it works: The invariant here is that intervals only do not overlap if one starts strictly after the other ends. Checking both conditions guarantees that any partial or full overlap, including touching at endpoints, is detected.

Python Solution

from typing import List

class Solution:
    def haveConflict(self, event1: List[str], event2: List[str]) -> bool:
        start1, end1 = event1
        start2, end2 = event2
        return start1 <= end2 and start2 <= end1

The implementation directly unpacks the event times and uses string comparison. In HH:MM format, string comparison works correctly because the lexicographical order of these strings matches the chronological order of times. This avoids any conversion to integers, keeping the solution simple and efficient.

Go Solution

func haveConflict(event1 []string, event2 []string) bool {
    start1, end1 := event1[0], event1[1]
    start2, end2 := event2[0], event2[1]
    return start1 <= end2 && start2 <= end1
}

The Go solution mirrors the Python solution. Go strings can be compared directly, and the <= operator works correctly for HH:MM format. This approach is concise and avoids parsing the strings into integers.

Worked Examples

Example 1:

event1 = ["01:15","02:00"]
event2 = ["02:00","03:00"]
start1 <= end2 → "01:15" <= "03:00" → True
start2 <= end1 → "02:00" <= "02:00" → True
Result → True

Example 2:

event1 = ["01:00","02:00"]
event2 = ["01:20","03:00"]
start1 <= end2 → "01:00" <= "03:00" → True
start2 <= end1 → "01:20" <= "02:00" → True
Result → True

Example 3:

event1 = ["10:00","11:00"]
event2 = ["14:00","15:00"]
start1 <= end2 → "10:00" <= "15:00" → True
start2 <= end1 → "14:00" <= "11:00" → False
Result → False

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only a constant number of comparisons are needed
Space	O(1)	Only variables for start and end times are used

The algorithm runs in constant time because there are always exactly two events. No additional data structures or conversions are necessary.

Test Cases

# Provided examples
assert Solution().haveConflict(["01:15","02:00"], ["02:00","03:00"]) == True
assert Solution().haveConflict(["01:00","02:00"], ["01:20","03:00"]) == True
assert Solution().haveConflict(["10:00","11:00"], ["14:00","15:00"]) == False

# Edge cases
assert Solution().haveConflict(["00:00","00:00"], ["00:00","00:00"]) == True # exact same time
assert Solution().haveConflict(["12:00","13:00"], ["13:01","14:00"]) == False # no overlap
assert Solution().haveConflict(["23:59","23:59"], ["23:59","23:59"]) == True # last minute of the day

Test	Why
["01:15","02:00"], ["02:00","03:00"]	Overlap at exact endpoint
["01:00","02:00"], ["01:20","03:00"]	Partial overlap inside first event
["10:00","11:00"], ["14:00","15:00"]	No overlap at all
["00:00","00:00"], ["00:00","00:00"]	Overlap at minimal time
["12:00","13:00"], ["13:01","14:00"]	Adjacent events with no overlap
["23:59","23:59"], ["23:59","23:59"]	Edge of day overlap

Edge Cases

Case 1: Exact same start and end time: Two events starting and ending at the same moment should count as overlapping. The algorithm handles this because both conditions start1 <= end2 and start2 <= end1 are true.

Case 2: Events touching at endpoints: If one event ends exactly when the other starts, this counts as a conflict due to the inclusive definition. The algorithm handles this because <= comparison captures equality.

Case 3: Minimal or maximal time values: Events starting at "00:00" or ending at "23:59" are valid. The algorithm works without any conversion because string comparison in HH:MM format respects chronological order, so no special handling for day boundaries is needed.