2409. Count Days Spent Together

EasyView on LeetCode

Math

Time: O(1)

Space: O(1)

Problem Overview

Alice and Bob each stay for one inclusive stretch of a non-leap year.

Intuition

Alice and Bob each stay for one inclusive stretch of a non-leap year. Once every MM-DD is a day number from 1 to 365, the question is how many days sit in both stretches. Two intervals overlap from the later arrival through the earlier departure. If the later arrival is after the earlier departure, they miss each other and the count is 0.

Algorithm

1Turn each date into a day of the year with a prefix of the twelve month lengths. January 1 is day 1 and December 31 is day 365.
2The shared start is the larger of the two arrival days.
3The shared end is the smaller of the two departure days.
4Return max(0, end - start + 1). The plus one counts both endpoints.

Example Walkthrough

Input: Alice 08-15 to 08-18, Bob 08-16 to 08-19

1.August 15 is day 227 and August 19 is day 231.
2.The later arrival is August 16 and the earlier departure is August 18.
3.Those three days, the 16th, 17th, and 18th, are the overlap.

Output: 3

Common Pitfalls

•The year has no February 29. Month lengths are the usual non-leap lengths.
•Both the arrival day and the departure day count. Dropping the plus one shortens every overlap.
•A later arrival after an earlier departure is zero days, not a negative number.
•Scanning all 365 days gives the same count, but the two endpoints already determine it.

2409.cs

// Approach: Convert each MM-DD to a day of the year with a prefix of month
// lengths. Both visits are inclusive intervals on that line, so the shared
// stretch is max(0, min(leave) - max(arrive) + 1).
// Time: O(1) Space: O(1)

public class Solution
{
    private static readonly int[] Prefix = { 0, 0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334 };

    public int CountDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob)
    {
        int start = Math.Max(Day(arriveAlice), Day(arriveBob));
        int end = Math.Min(Day(leaveAlice), Day(leaveBob));
        return Math.Max(0, end - start + 1);
    }

    private static int Day(string s)
    {
        int month = (s[0] - '0') * 10 + (s[1] - '0');
        int day = (s[3] - '0') * 10 + (s[4] - '0');
        return Prefix[month] + day;
    }
}

Was this solution helpful?