# Determine if Two Events Have Conflict
**Difficulty:** EASY
[External](https://leetcode.com/problems/determine-if-two-events-have-conflict)
Canonical: https://scaleengineer.com/dsa/problems/determine-if-two-events-have-conflict
**Data structures:** Array, String
**Companies:** [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs)
---
## Problem
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:**

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

# Approaches
## Convert to Minutes and Compare
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.
**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.
**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.
### Explanation
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:
```java
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;
    }
}
```
### 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 `event1` and `event2` into four integer variables: `start1`, `end1`, `start2`, `end2`.
- An overlap occurs if `event1` does not end before `event2` starts AND `event2` does not end before `event1` starts.
- This translates to the boolean condition: `start1 <= end2 && start2 <= end1`.
- Return the result of this comparison.

## Direct Lexicographical 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.
**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.
**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.
### Explanation
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:
```java
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;
    }
}
```
### Algorithm
- Get the start and end time strings for both events.
- The condition for overlap between two intervals `[start1, end1]` and `[start2, end2]` is `start1 <= end2` and `start2 <= 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]) <= 0` and `event2[0].compareTo(event1[1]) <= 0`.
- Return the result of this boolean expression.

# Solutions
### Java

```java
class Solution {
public
  boolean haveConflict(String[] event1, String[] event2) {
    return !(event1[0].compareTo(event2[1]) > 0 ||
             event1[1].compareTo(event2[0]) < 0);
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool haveConflict(vector<string> &event1, vector<string> &event2) {
    return !(event1[0] > event2[1] || event1[1] < event2[0]);
  }
};

```

### Python

```python
class Solution:
    def haveConflict(self, event1: List[str], event2: List[str]) -> bool: return not (
        event1[0] > event2[1] or event1[1] < event2[0])

```