Alice and Bob are traveling to Rome for separate business meetings.
You are given 4 strings arriveAlice, leaveAlice, arriveBob, and leaveBob. Alice will be in the city from the dates arriveAlice to leaveAlice (inclusive), while Bob will be in the city from the dates arriveBob to leaveBob (inclusive). Each will be a 5-character string in the format "MM-DD", corresponding to the month and day of the date.
Return the total number of days that Alice and Bob are in Rome together.
You can assume that all dates occur in the same calendar year, which is not a leap year. Note that the number of days per month can be represented as: [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31].
Example 1:
Input: arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19" Output: 3 Explanation: Alice will be in Rome from August 15 to August 18. Bob will be in Rome from August 16 to August 19. They are both in Rome together on August 16th, 17th, and 18th, so the answer is 3.
Example 2:
Input: arriveAlice = "10-01", leaveAlice = "10-31", arriveBob = "11-01", leaveBob = "12-31" Output: 0 Explanation: There is no day when Alice and Bob are in Rome together, so we return 0.
Constraints:
"MM-DD".In #2409 Count Days Spent Together, Alice and Bob each provide arrival and leaving dates in MM-DD format. The task is to determine how many days both people are on vacation at the same time.
A practical approach is to convert each date into a day-of-year number. You can maintain an array of the number of days in each month and compute the cumulative day count up to the given month, then add the day value. Once all four dates are converted, the overlapping period can be determined using max(startAlice, startBob) and min(endAlice, endBob).
If the start of the overlap is less than or equal to the end, the number of shared days is the difference plus one (since the dates are inclusive). Otherwise, there is no overlap. Because the month lengths are fixed and the calculations are constant, this method runs efficiently with O(1) time and O(1) space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Convert dates to day-of-year and compute overlap | O(1) | O(1) |
Dave Burji
Use these hints if you're stuck. Try solving on your own first.
For a given day, determine if Alice or Bob or both are in Rome.
Brute force all 365 days for both Alice and Bob.
Watch expert explanations and walkthroughs
Jot down your thoughts, approach, and key learnings
Converting to day-of-year simplifies comparisons between dates. Instead of comparing months and days separately, each date becomes a single integer, making it easy to compute overlaps with simple math.
Problems like this are commonly used in interviews to test basic date manipulation, string parsing, and interval overlap logic. While the exact question may vary, similar interval problems appear in FAANG-style interviews.
A simple array storing the number of days in each month is sufficient. It helps convert month-day strings into cumulative day-of-year values quickly without needing complex data structures.
The optimal approach converts each MM-DD date into a day-of-year value using a predefined list of days per month. After conversion, compute the overlapping range using max(start) and min(end). If the overlap is valid, return the inclusive difference.