Skip to content

2409. Count Days Spent Together

SourceBiweekly Contest 87 Q1DifficultyEasyRating1562

Description

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:

  • 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.

Solutions

Solution 1: Prefix Sum

Thinking

Days together are the length of the intersection of two closed intervals. Scanning every day of the year fits the constraints, but the inputs are \(\texttt{MM-DD}\) strings, so both comparison and counting need one shared index.

Adding the preceding month lengths on each conversion repeats the same constant work. Lexicographic order of this format matches the calendar, so the overlap runs from the later arrival to the earlier departure. Month lengths in a non-leap year are fixed; once their prefix sums \(f\) are known, month \(m\) and day \(d\) is day \(f_{m-1}+d\) of the year.

The two endpoints are converted through \(f\), then subtracted and adjusted by one. If the start falls after the end, the intersection is empty.

We take the later arrival and the earlier departure, map both dates to a day of the year with the month-length prefix, and return the length of that closed interval.

The time complexity is \(O(1)\), and the space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
f = list(accumulate([31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31], initial=0))


class Solution:
    def countDaysTogether(
        self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str
    ) -> int:
        start = max(arriveAlice, arriveBob)
        end = min(leaveAlice, leaveBob)
        d1 = f[int(start[:2]) - 1] + int(start[3:])
        d2 = f[int(end[:2]) - 1] + int(end[3:])
        return max(d2 - d1 + 1, 0)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    static final int[] f = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};

    public int countDaysTogether(
        String arriveAlice, String leaveAlice, String arriveBob, String leaveBob) {
        String start = arriveAlice.compareTo(arriveBob) > 0 ? arriveAlice : arriveBob;
        String end = leaveAlice.compareTo(leaveBob) < 0 ? leaveAlice : leaveBob;
        int d1
            = f[Integer.parseInt(start.substring(0, 2)) - 1] + Integer.parseInt(start.substring(3));
        int d2 = f[Integer.parseInt(end.substring(0, 2)) - 1] + Integer.parseInt(end.substring(3));
        return Math.max(d2 - d1 + 1, 0);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    static constexpr int f[] = {0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334};

    int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob, string leaveBob) {
        string start = max(arriveAlice, arriveBob);
        string end = min(leaveAlice, leaveBob);
        int d1 = f[stoi(start.substr(0, 2)) - 1] + stoi(start.substr(3));
        int d2 = f[stoi(end.substr(0, 2)) - 1] + stoi(end.substr(3));
        return max(d2 - d1 + 1, 0);
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
var f = [12]int{0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334}

func countDaysTogether(arriveAlice string, leaveAlice string, arriveBob string, leaveBob string) int {
    start := arriveAlice
    if arriveBob > start {
        start = arriveBob
    }
    end := leaveAlice
    if leaveBob < end {
        end = leaveBob
    }
    d1 := f[int(start[0]-'0')*10+int(start[1]-'0')-1] + int(start[3]-'0')*10 + int(start[4]-'0')
    d2 := f[int(end[0]-'0')*10+int(end[1]-'0')-1] + int(end[3]-'0')*10 + int(end[4]-'0')
    return max(d2-d1+1, 0)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
const f = [0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334];

function countDaysTogether(
    arriveAlice: string,
    leaveAlice: string,
    arriveBob: string,
    leaveBob: string,
): number {
    const start = arriveAlice > arriveBob ? arriveAlice : arriveBob;
    const end = leaveAlice < leaveBob ? leaveAlice : leaveBob;
    const d1 = f[Number(start.slice(0, 2)) - 1] + Number(start.slice(3));
    const d2 = f[Number(end.slice(0, 2)) - 1] + Number(end.slice(3));
    return Math.max(d2 - d1 + 1, 0);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
impl Solution {
    pub fn count_days_together(
        arrive_alice: String,
        leave_alice: String,
        arrive_bob: String,
        leave_bob: String,
    ) -> i32 {
        let f = [0, 31, 59, 90, 120, 151, 181, 212, 243, 273, 304, 334];
        let start = arrive_alice.max(arrive_bob);
        let end = leave_alice.min(leave_bob);
        let d1 = f[start[..2].parse::<usize>().unwrap() - 1] + start[3..].parse::<i32>().unwrap();
        let d2 = f[end[..2].parse::<usize>().unwrap() - 1] + end[3..].parse::<i32>().unwrap();
        (d2 - d1 + 1).max(0)
    }
}

Comments