algoadvance

Leetcode 2446. Determine if Two Events Have Conflict

Problem Statement

You are given two events in the form of two pairs of strings: event1 and event2. Each string represents an event time in the format "HH:MM". Your goal is to determine if these two events conflict with each other. Two events conflict if they overlap in time.

For example:

In this case, the two events have a conflict because they overlap from 10:30 to 11:00.

Clarifying Questions

  1. Time format: Is the time format always guaranteed to be in "HH:MM" and in 24-hour time format?
    • Yes.
  2. Same time events: If two events start or end exactly at the same time, do they conflict?
    • Yes, if one event starts at the same time another ends, they are considered to conflict.
  3. Order of events: Is event1 always before event2 in the input order?
    • Input order does not matter. The events may or may not be in any time order.

Strategy

  1. Convert Time to Minutes:
    • Convert the "HH:MM" format to total minutes from 00:00 for easy comparison.
  2. Compare Events:
    • Check if the two events overlap by comparing their start and end times.

Code

#include <iostream>
#include <vector>
#include <string>

using namespace std;

// Function to convert "HH:MM" to minutes from "00:00"
int convertToMinutes(const string &time) {
    int hours = stoi(time.substr(0, 2));
    int minutes = stoi(time.substr(3, 2));
    return hours * 60 + minutes;
}

// Function to determine if two events have a conflict
bool haveConflict(vector<string>& event1, vector<string>& event2) {
    int start1 = convertToMinutes(event1[0]);
    int end1 = convertToMinutes(event1[1]);
    int start2 = convertToMinutes(event2[0]);
    int end2 = convertToMinutes(event2[1]);
    
    // Check if the events do not overlap
    // If one event starts after the other ends, they do not overlap
    if (end1 <= start2 || end2 <= start1) {
        return false;
    }

    // They overlap otherwise
    return true;
}

int main() {
    vector<string> event1 = {"10:00", "11:00"};
    vector<string> event2 = {"10:30", "12:00"};
    
    bool conflict = haveConflict(event1, event2);
    cout << (conflict ? "Conflict" : "No Conflict") << endl;

    return 0;
}

Explanation

  1. Conversion Function:
    • The convertToMinutes function converts a time string in "HH:MM" format to the total minutes from midnight.
  2. Conflict Function:
    • The haveConflict function calculates the start and end times of both events in minutes.
    • It then checks if the intervals [start1, end1) and [start2, end2) do not overlap. If end1 <= start2 or end2 <= start1, the events do not overlap. Otherwise, they do.
  3. Main Function:
    • We use main to test our solution with sample inputs.

Time Complexity

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