algoadvance

Leetcode 2409. Count Days Spent Together

Problem Statement

You are given four strings arriveAlice, leaveAlice, arriveBob, and leaveBob, representing the arrival and departure dates of Alice and Bob respectively. All dates are in the format MM-DD. You need to find the number of days Alice and Bob spend together.

Clarifying Questions

  1. Date Format and Year Consideration: All dates are within the same year, and the year is non-leap.
  2. Guaranteed Valid Dates: No need to check for invalid dates; assume all provided dates are valid.
  3. Time Constraints: What is the maximum length of strings? Usually given constraints are reasonable for standard library date operations.

Strategy

  1. Convert Dates to Days:
    • Use a function that converts a MM-DD string to the number of days from the start of the year. This avoids dealing with month boundaries repeatedly.
  2. Intersection of Date Ranges:
    • Calculate the intersection of the date ranges for Alice and Bob.
    • Use the maximum of starting dates as the start of the overlap.
    • Use the minimum of ending dates as the end of the overlap.
  3. Calculate Duration:
    • If the start of the overlap is before or the same as the end, calculate the number of days in between and include both end days.

C++ Code

#include <string>
#include <algorithm>

using namespace std;

// Convert date from MM-DD to the day of the year
int convertToDayOfYear(const string& date) {
    int month = stoi(date.substr(0, 2));
    int day = stoi(date.substr(3, 2));
    
    // Non-leap year days till each month end
    static const int daysTillMonthEnd[13] = {
        0,   // dummy month (0)
        31,  // Jan
        59,  // Feb
        90,  // Mar
        120, // Apr
        151, // May
        181, // Jun
        212, // Jul
        243, // Aug
        273, // Sep
        304, // Oct
        334, // Nov
        365  // Dec
    };
    
    return daysTillMonthEnd[month - 1] + day;
}

int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
    int aliceStart = convertToDayOfYear(arriveAlice);
    int aliceEnd = convertToDayOfYear(leaveAlice);
    int bobStart = convertToDayOfYear(arriveBob);
    int bobEnd = convertToDayOfYear(leaveBob);
    
    // Calculate intersection period
    int startOverlap = max(aliceStart, bobStart);
    int endOverlap = min(aliceEnd, bobEnd);
    
    // Calculate number of overlap days
    if (startOverlap > endOverlap) {
        return 0; // No overlap
    } else {
        return endOverlap - startOverlap + 1;
    }
}

Time Complexity

This solution efficiently calculates the number of overlapping days between two date ranges within a given year.

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