Determine if Two Events Have Conflict
EasyPrompt
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]andevent2 = [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:
event1.length == event2.length == 2event1[i].length == event2[i].length == 5startTime1 <= endTime1startTime2 <= endTime2- All the event times follow the
HH:MMformat.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach involves converting the time strings from the "HH:MM" format into a numerical representation, specifically the total number of minutes from midnight. This transformation allows for straightforward numerical comparison of the time intervals.
Algorithm
- Define a helper function
convertToMinutes(timeStr)that parses a "HH:MM" string and returns the total minutes from midnight (HH * 60 + MM). - Call this function to convert the start and end times of both
event1andevent2into four integer variables:start1,end1,start2,end2. - An overlap occurs if
event1does not end beforeevent2starts ANDevent2does not end beforeevent1starts. - This translates to the boolean condition:
start1 <= end2 && start2 <= end1. - Return the result of this comparison.
Walkthrough
The core idea is to handle time as a single integer value, which simplifies comparisons. A time "HH:MM" can be converted to HH * 60 + MM minutes.
We apply this conversion to the start and end times of both events. Let's say event1 becomes [s1, e1] and event2 becomes [s2, e2], where these are all integer values representing minutes.
Two events conflict if their time intervals overlap. Two intervals [s1, e1] and [s2, e2] overlap if and only if the start of one is before or at the same time as the end of the other, for both events. Mathematically, this is expressed as s1 <= e2 AND s2 <= e1.
Here is the implementation:
class Solution { public boolean haveConflict(String[] event1, String[] event2) { int start1 = convertToMinutes(event1[0]); int end1 = convertToMinutes(event1[1]); int start2 = convertToMinutes(event2[0]); int end2 = convertToMinutes(event2[1]); // Check for overlap condition: start1 <= end2 AND start2 <= end1 return start1 <= end2 && start2 <= end1; } private int convertToMinutes(String time) { // "HH:MM" int hours = Integer.parseInt(time.substring(0, 2)); int minutes = Integer.parseInt(time.substring(3, 5)); return hours * 60 + minutes; }}Complexity
Time
O(1) - The number of operations is constant. We perform a fixed number of string manipulations (substring), integer conversions (parseInt), arithmetic operations, and comparisons, none of which depend on the size of the input.
Space
O(1) - We use a few integer variables to store the converted times. The space used does not scale with the input size.
Trade-offs
Pros
The logic is very clear, explicit, and easy to understand.
This approach is robust and can be easily adapted if calculations involving time durations are needed.
Cons
Involves string parsing and integer conversions, which might have slightly more computational overhead than direct string comparison.
This approach leverages the fact that the time strings are in a format ("HH:MM") that is naturally sortable. Lexicographical comparison of these strings is equivalent to chronological comparison. This allows us to check for overlap by directly comparing the string representations of the start and end times.
Algorithm
- Get the start and end time strings for both events.
- The condition for overlap between two intervals
[start1, end1]and[start2, end2]isstart1 <= end2andstart2 <= end1. - Since the time format "HH:MM" is lexicographically comparable, we can use string comparison directly.
- In Java, this translates to
event1[0].compareTo(event2[1]) <= 0andevent2[0].compareTo(event1[1]) <= 0. - Return the result of this boolean expression.
Walkthrough
The problem provides times in "HH:MM" format. This format has a fixed length, and the hours and minutes are zero-padded (e.g., "01" instead of "1"). This property means that comparing two time strings lexicographically (alphabetically) will yield the same result as comparing them chronologically. For example, "09:30" comes before "10:00" both chronologically and lexicographically.
We can use the same logic for checking interval overlap: two intervals [start1, end1] and [start2, end2] overlap if start1 <= end2 and start2 <= end1.
Instead of converting to numbers, we can perform these comparisons directly on the strings using a standard string comparison function (like compareTo in Java), which returns a value less than or equal to 0 if the first string is lexicographically less than or equal to the second.
Here is the implementation:
class Solution { public boolean haveConflict(String[] event1, String[] event2) { // String.compareTo() can be used because the "HH:MM" format is // fixed-width and zero-padded, making lexicographical comparison // equivalent to chronological comparison. // A conflict exists if event1 starts before or at the same time event2 ends, // AND event2 starts before or at the same time event1 ends. // start1 <= end2 is equivalent to event1[0].compareTo(event2[1]) <= 0 // start2 <= end1 is equivalent to event2[0].compareTo(event1[1]) <= 0 return event1[0].compareTo(event2[1]) <= 0 && event2[0].compareTo(event1[1]) <= 0; }}Complexity
Time
O(1) - The `compareTo` method on strings of a fixed, small length (5 characters) takes constant time. The overall number of operations is constant.
Space
O(1) - We only use a few string references, which requires constant extra space.
Trade-offs
Pros
Extremely concise and elegant code.
Potentially faster due to avoiding parsing, type conversions, and arithmetic operations. It directly compares the raw input.
Cons
This approach relies on the specific properties of the input string format ("HH:MM"). It might not work if the format was different (e.g., "H:M" without zero-padding).
The logic might seem less intuitive to someone not familiar with the properties of lexicographical comparison for this specific format.
Solutions
Solution
class Solution {public boolean haveConflict(String[] event1, String[] event2) { return !(event1[0].compareTo(event2[1]) > 0 || event1[1].compareTo(event2[0]) < 0); }}class Solution {public: bool haveConflict(vector<string> &event1, vector<string> &event2) { return !(event1[0] > event2[1] || event1[1] < event2[0]); }};class Solution: def haveConflict(self, event1: List[str], event2: List[str]) -> bool: return not ( event1[0] > event2[1] or event1[1] < event2[0])Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.