#2409

Easy

LeetCode Problem Workspace

Count Days Spent Together

Count the total number of days Alice and Bob are in Rome together, given their arrival and departure dates.

Problem Statement

Alice and Bob are traveling to Rome for separate business meetings. Each has specific arrival and departure dates in the format 'MM-DD'. You are provided four strings: arriveAlice, leaveAlice, arriveBob, and leaveBob. Alice is in Rome from arriveAlice to leaveAlice, and Bob is in Rome from arriveBob to leaveBob.

Your task is to return the number of days they both spend in Rome together. The days of overlap between their stays need to be calculated. The dates are valid and lie within a non-leap year, and the format follows 'MM-DD'.

Examples

Example 1

Input: arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"

Output: 3

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

There is no day when Alice and Bob are in Rome together, so we return 0.

Constraints

All dates are provided in the format "MM-DD".
Alice and Bob's arrival dates are earlier than or equal to their leaving dates.
The given dates are valid dates of a non-leap year.

Solution Approach

Parse and Convert Dates

First, convert the given 'MM-DD' date strings into a comparable format, such as the number of days since the start of the year. This allows easier comparison of the dates to calculate overlap.

Calculate Overlap

Find the maximum of the two arrival dates and the minimum of the two departure dates. If the maximum arrival date is earlier than or equal to the minimum departure date, then calculate the number of overlapping days.

Return the Result

If the calculated overlap is positive, return the number of days; otherwise, return zero, as no days overlap.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on how the date conversion and comparison are handled. Parsing and comparing two date ranges results in a time complexity of O(1), and no additional space is required beyond storing the date values, so the space complexity is O(1).

What Interviewers Usually Probe

Can the candidate efficiently convert the string dates into a comparable format?
Does the candidate correctly handle edge cases where no overlap exists?
Does the candidate optimize for simplicity and correctness in their approach?

Common Pitfalls or Variants

Common pitfalls

Not correctly handling the case where there is no overlap, leading to a negative number of days.
Incorrectly parsing the date strings or mishandling the format.
Overcomplicating the solution by adding unnecessary steps or operations.

Follow-up variants

Consider cases with varying day lengths such as when the overlap occurs in the same month versus spanning multiple months.
Extend the problem to include multiple people, calculating the total overlap for all travelers.
Modify the problem to work with leap years or other calendar systems.

FAQ

How do I calculate the overlap between Alice and Bob's travel dates?

To calculate the overlap, find the later of their arrival dates and the earlier of their departure dates. If the later arrival date is before or equal to the earlier departure date, the number of overlapping days is the difference between these dates.

What is the time complexity of this problem?

The time complexity is O(1), as the task involves a constant number of operations to parse the dates and calculate the overlap.

How should I handle cases where Alice and Bob's dates do not overlap?

In such cases, you should return zero as no days overlap between their stays.

Can I use built-in date parsing functions for this problem?

Yes, using built-in date functions is a valid approach as long as you can properly convert the string into a comparable format like 'YYYY-MM-DD' or days of the year.

What is the primary pattern of this problem?

The primary pattern of this problem is calculating the intersection of two date ranges, which involves simple comparison and arithmetic to find the overlap.

terminal

Solution

Solution 1: Simulation

We convert the dates into days, and then calculate the number of days both people are in Rome.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countDaysTogether(
        self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str
    ) -> int:
        a = max(arriveAlice, arriveBob)
        b = min(leaveAlice, leaveBob)
        days = (31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
        x = sum(days[: int(a[:2]) - 1]) + int(a[3:])
        y = sum(days[: int(b[:2]) - 1]) + int(b[3:])
        return max(y - x + 1, 0)

Continue Practicing

#2514 count anagrams #2269 find the k beauty of a number #2266 count number of texts