LeetCode Solutions Blog

Count Days Spent Together

Number: 2496

Difficulty: Easy

Paid? No

Companies: N/A

Problem Description

Alice and Bob have their travel schedules to Rome specified by arrival and departure dates in the "MM-DD" format. Both will stay in Rome on all days from their arrival date to their departure date (inclusive). The goal is to find out how many days both are in Rome together.

Key Insights

Convert the "MM-DD" string into a day-of-year representation using an array of days per month.
Determine the overlapping period by taking the maximum of both arrival dates and the minimum of both departure dates.
The total overlapping days is the difference plus one, and if there is no overlap, return zero.

Space and Time Complexity

Time Complexity: O(1) – The solution involves a constant amount of work. Space Complexity: O(1) – Only a fixed number of variables are used and no extra space is required.

Solution

We start by converting each date from the "MM-DD" format into its numerical day-of-year equivalent. This is done by precomputing the number of days in each month for a non-leap year. Once every date is converted, the overlapping period is simply the period from the later arrival date (maximum of both arrival days) to the earlier departure date (minimum of both departure days). If the calculated overlap is negative, it means there is no period when both are in Rome together. Otherwise, the number of days spent together is the difference between the overlapping end and start plus one.

Code Solutions

# Function to convert date string "MM-DD" to day-of-year
def convert_date_to_day(date_str):
    # Days per month for a non-leap year.
    days_per_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
    # Split the date string into month and day components.
    month, day = map(int, date_str.split('-'))
    # Calculate the day-of-year by summing up days in the preceding months and adding the current day.
    days_before_month = sum(days_per_month[:month - 1])
    return days_before_month + day

def count_days_spent_together(arriveAlice, leaveAlice, arriveBob, leaveBob):
    # Convert all dates to day-of-year numbers.
    alice_start = convert_date_to_day(arriveAlice)
    alice_end = convert_date_to_day(leaveAlice)
    bob_start = convert_date_to_day(arriveBob)
    bob_end = convert_date_to_day(leaveBob)
    
    # Determine the overlapping period.
    start_overlap = max(alice_start, bob_start)
    end_overlap = min(alice_end, bob_end)
    
    # If there is no overlap, return 0.
    if start_overlap > end_overlap:
        return 0
    
    # Otherwise, return the number of overlapping days (inclusive).
    return end_overlap - start_overlap + 1

# Example usage:
print(count_days_spent_together("08-15", "08-18", "08-16", "08-19"))  # Expected output: 3