algoadvance

You are given four dates: arriveAlice, leaveAlice, arriveBob, and leaveBob. These dates denote the arrival and departure dates of Alice and Bob in MM-DD format. You need to determine how many days Alice and Bob spend together.

Clarifying Questions

1. Date Format Consistency: Are the dates in MM-DD format guaranteed to be valid and within a single year?
2. Year Considerations: Should we consider leap years, or do we assume all dates fall within a non-leap year?
3. Edge Cases: Should we handle cases where the arrival date is after the leave date, or can we assume proper formatted intervals?

Assuming the following based on common constraints in such problems:

• All dates are valid and within the same year.
• We assume all dates are on a non-leap year.

Strategy

1. Convert Dates to Integer Days: Convert each date into a single integer representing the day of the year.
2. Intersection of Ranges: Calculate the overlapping range between Alice’s and Bob’s stays.
3. Count Overlapping Days: Compute the number of days in the overlapping range.

Steps:

1. Create a helper function to convert the date (MM-DD) to the day of the year.
2. Compute the start and end of the overlap using the maximum start date and the minimum end date.
3. Calculate the number of overlapping days by subtracting the start from the end of the overlap and adding one if they overlap.

Code

def countDaysTogether(arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
    def dateToDayOfYear(date: str) -> int:
        month, day = map(int, date.split('-'))
        days_in_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
        return sum(days_in_month[:month-1]) + day
    
    arriveAliceDay = dateToDayOfYear(arriveAlice)
    leaveAliceDay = dateToDayOfYear(leaveAlice)
    arriveBobDay = dateToDayOfYear(arriveBob)
    leaveBobDay = dateToDayOfYear(leaveBob)
    
    startOverlap = max(arriveAliceDay, arriveBobDay)
    endOverlap = min(leaveAliceDay, leaveBobDay)
    
    if startOverlap > endOverlap:
        return 0
    
    return endOverlap - startOverlap + 1

# Example Usage:
arriveAlice = "08-15"
leaveAlice = "08-18"
arriveBob = "08-16"
leaveBob = "08-19"
print(countDaysTogether(arriveAlice, leaveAlice, arriveBob, leaveBob))  # Output: 3

Time Complexity

• Convert date to day of year: O(1) for each date since it’s a simple set of operations.
• Overall Complexity: O(1), because the number of operations is constant regardless of input size.

The solution efficiently calculates the overlapping days using straightforward arithmetic and date conversion, ensuring optimal performance for the given problem constraints.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?