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.

#2409

Easy

auto_awesome数学·string

LeetCode 题解工作台

统计共同度过的日子数

Alice 和 Bob 计划分别去罗马开会。给你四个字符串 arriveAlice ， leaveAlice ， arriveBob 和 leaveBob 。Alice 会在日期 arriveAlice 到 leaveAlice 之间在城市里（日期为闭区间），而 Bob 在日期 arriveB…

数学字符串

题目描述

Alice 和 Bob 计划分别去罗马开会。

给你四个字符串 arriveAlice ，leaveAlice ，arriveBob 和 leaveBob 。Alice 会在日期 arriveAlice 到 leaveAlice 之间在城市里（日期为闭区间），而 Bob 在日期 arriveBob 到 leaveBob 之间在城市里（日期为闭区间）。每个字符串都包含 5 个字符，格式为 "MM-DD" ，对应着一个日期的月和日。

请你返回 Alice和 Bob 同时在罗马的天数。

你可以假设所有日期都在 同一个 自然年，而且不是闰年。每个月份的天数分别为：[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] 。

示例 1：

输入：arriveAlice = "08-15", leaveAlice = "08-18", arriveBob = "08-16", leaveBob = "08-19"
输出：3
解释：Alice 从 8 月 15 号到 8 月 18 号在罗马。Bob 从 8 月 16 号到 8 月 19 号在罗马，他们同时在罗马的日期为 8 月 16、17 和 18 号。所以答案为 3 。

示例 2：

输入：arriveAlice = "10-01", leaveAlice = "10-31", arriveBob = "11-01", leaveBob = "12-31"
输出：0
解释：Alice 和 Bob 没有同时在罗马的日子，所以我们返回 0 。

提示：

所有日期的格式均为 "MM-DD" 。
Alice 和 Bob 的到达日期都 早于或等于 他们的离开日期。
题目测试用例所给出的日期均为 非闰年 的有效日期。

lightbulb

解题思路

方法一：模拟

我们将日期转换为天数，然后计算两个人在罗马的天数。

时间复杂度 $O(C)$ ，空间复杂度 $O(C)$ 。其中 $C$ 为常数。

1

2

3

4

5

6

7

8

9

10

11

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)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

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

warning

常见陷阱

外企场景

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

swap_horiz

进阶变体

外企场景

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

help

常见问题

外企场景

继续练习

#2514 统计同位异构字符串数目 #2269 找到一个数字的 K 美丽值 #2266 统计打字方案数