algoadvance

Leetcode 2446. Determine if Two Events Have Conflict

Problem Statement

You are given two arrays of strings event1 and event2 where:

Event times are given in the format “HH:MM”.

Determine if the two events have a conflict, meaning they overlap in time.

Return true if there is a conflict between the two events, and false otherwise.

Clarifying Questions

  1. Is each time guaranteed to be in the “HH:MM” 24-hour format?
    • Yes.
  2. Can the times for an individual event cross midnight and make dates relevant?
    • No, the times will be within a single day (00:00 to 23:59).

Strategy

  1. Parse the Input Times: Convert the start and end times of each event from “HH:MM” format to a comparable format such as the number of minutes since midnight.
  2. Compare Intervals: Check if the time intervals [startTime1, endTime1] and [startTime2, endTime2] overlap.
    • Two intervals [start1, end1] and [start2, end2] overlap if start1 < end2 and start2 < end1.

Code

public class EventConflict {
    public boolean haveConflict(String[] event1, String[] event2) {
        int start1 = toMinutes(event1[0]);
        int end1 = toMinutes(event1[1]);
        int start2 = toMinutes(event2[0]);
        int end2 = toMinutes(event2[1]);

        // Check if there is an overlap
        return start1 < end2 && start2 < end1;
    }

    private int toMinutes(String time) {
        String[] parts = time.split(":");
        int hours = Integer.parseInt(parts[0]);
        int minutes = Integer.parseInt(parts[1]);
        return hours * 60 + minutes;
    }

    public static void main(String[] args) {
        EventConflict ec = new EventConflict();
        String[] event1 = {"01:15", "02:00"};
        String[] event2 = {"02:00", "03:00"};
        System.out.println(ec.haveConflict(event1, event2)); // Output should be true
    }
}

Explanation

  1. Conversion Function: toMinutes converts “HH:MM” time into minutes since midnight.
  2. Conflict Check: We then check if one event starts before the other ends and vice versa to determine an overlap.

Time Complexity

The time complexity is O(1) because it involves only a constant amount of work (parsing a few strings and basic comparisons).

The space complexity is also O(1) because we only use a fixed amount of additional memory regardless of the input size.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI