Easy

题目描述

Alice 和 Bob 要前往罗马参加各自的商务会议。

给你 4 个字符串 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 的到达日期早于或等于他们的离开日期
  • 给定的日期是非闰年的有效日期

解题思路

这道题需要计算两个时间区间的重叠天数。关键思路是将日期转换为一年中的第几天，然后计算区间重叠。

核心思路：

  1. 日期转换：将 "MM-DD" 格式的日期转换为一年中的第几天（1-365）
  2. 区间重叠：计算两个闭区间 [start1, end1] 和 [start2, end2] 的重叠长度
  3. 重叠计算公式：max(0, min(end1, end2) - max(start1, start2) + 1)

解法分析：

  • 暴力法：遍历一年中的每一天，检查是否同时在两人的区间内，时间复杂度 O(365)
  • 数学法（推荐）：直接计算区间重叠，时间复杂度 O(1)

数学法更优雅且高效。重叠区间的起始日期是两人到达日期的较大值，结束日期是两人离开日期的较小值。如果起始日期大于结束日期，则没有重叠。

实现要点：

  • 建立月份天数数组：[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
  • 日期转换函数：累加月份天数 + 当前月的天数
  • 使用数学公式直接计算重叠天数

代码实现

class Solution {
public:
    int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
        vector<int> daysInMonth = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        
        auto dayOfYear = [&](string date) -> int {
            int month = stoi(date.substr(0, 2));
            int day = stoi(date.substr(3, 2));
            int result = day;
            for (int i = 0; i < month - 1; i++) {
                result += daysInMonth[i];
            }
            return result;
        };
        
        int aliceStart = dayOfYear(arriveAlice);
        int aliceEnd = dayOfYear(leaveAlice);
        int bobStart = dayOfYear(arriveBob);
        int bobEnd = dayOfYear(leaveBob);
        
        int overlapStart = max(aliceStart, bobStart);
        int overlapEnd = min(aliceEnd, bobEnd);
        
        return max(0, overlapEnd - overlapStart + 1);
    }
};

class Solution:
    def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
        days_in_month = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]
        
        def day_of_year(date):
            month, day = map(int, date.split('-'))
            return sum(days_in_month[:month-1]) + day
        
        alice_start = day_of_year(arriveAlice)
        alice_end = day_of_year(leaveAlice)
        bob_start = day_of_year(arriveBob)
        bob_end = day_of_year(leaveBob)
        
        overlap_start = max(alice_start, bob_start)
        overlap_end = min(alice_end, bob_end)
        
        return max(0, overlap_end - overlap_start + 1)

public class Solution {
    public int CountDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
        int[] daysInMonth = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        
        int DayOfYear(string date) {
            var parts = date.Split('-');
            int month = int.Parse(parts[0]);
            int day = int.Parse(parts[1]);
            int result = day;
            for (int i = 0; i < month - 1; i++) {
                result += daysInMonth[i];
            }
            return result;
        }
        
        int aliceStart = DayOfYear(arriveAlice);
        int aliceEnd = DayOfYear(leaveAlice);
        int bobStart = DayOfYear(arriveBob);
        int bobEnd = DayOfYear(leaveBob);
        
        int overlapStart = Math.Max(aliceStart, bobStart);
        int overlapEnd = Math.Min(aliceEnd, bobEnd);
        
        return Math.Max(0, overlapEnd - overlapStart + 1);
    }
}

var countDaysTogether = function(arriveAlice, leaveAlice, arriveBob, leaveBob) {
    const daysInMonth = [31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
    
    const dayOfYear = (date) => {
        const [month, day] = date.split('-').map(Number);
        let result = day;
        for (let i = 0; i < month - 1; i++) {
            result += daysInMonth[i];
        }
        return result;
    };
    
    const aliceStart = dayOfYear(arriveAlice);
    const aliceEnd = dayOfYear(leaveAlice);
    const bobStart = dayOfYear(arriveBob);
    const bobEnd = dayOfYear(leaveBob);
    
    const overlapStart = Math.max(aliceStart, bobStart);
    const overlapEnd = Math.min(aliceEnd, bobEnd);
    
    return Math.max(0, overlapEnd - overlapStart + 1);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(1)
空间复杂度O(1)

相关题目