Problem

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

Examples

Example 1

1
2
3
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

1
2
3
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.

Solution

Method 1 – Interval Overlap Calculation

Intuition

The days Alice and Bob spend together are the overlapping days between their two date intervals. We can convert the dates to day-of-year numbers and compute the overlap.

Approach

  1. Convert each date string (MM-DD) to a day-of-year integer using a prefix sum of days per month.
  2. The overlap interval is from max(arriveAlice, arriveBob) to min(leaveAlice, leaveBob).
  3. If the overlap is valid, the answer is (end - start + 1), else 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    int countDaysTogether(string aA, string lA, string aB, string lB) {
        vector<int> days = {0,31,59,90,120,151,181,212,243,273,304,334,365};
        auto f = [&](string d) {
            int m = stoi(d.substr(0,2)), dd = stoi(d.substr(3,2));
            return days[m-1] + dd;
        };
        int s = max(f(aA), f(aB)), e = min(f(lA), f(lB));
        return max(0, e - s + 1);
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func countDaysTogether(aA, lA, aB, lB string) int {
    days := []int{0,31,59,90,120,151,181,212,243,273,304,334,365}
    f := func(d string) int {
        m := (int(d[0]-'0')*10 + int(d[1]-'0'))
        dd := (int(d[3]-'0')*10 + int(d[4]-'0'))
        return days[m-1] + dd
    }
    s := max(f(aA), f(aB))
    e := min(f(lA), f(lB))
    if s > e { return 0 }
    return e - s + 1
}
func max(a, b int) int { if a > b { return a }; return b }
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    public int countDaysTogether(String aA, String lA, String aB, String lB) {
        int[] days = {0,31,59,90,120,151,181,212,243,273,304,334,365};
        java.util.function.Function<String, Integer> f = d -> {
            int m = Integer.parseInt(d.substring(0,2)), dd = Integer.parseInt(d.substring(3,5));
            return days[m-1] + dd;
        };
        int s = Math.max(f.apply(aA), f.apply(aB)), e = Math.min(f.apply(lA), f.apply(lB));
        return Math.max(0, e - s + 1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution {
    fun countDaysTogether(aA: String, lA: String, aB: String, lB: String): Int {
        val days = listOf(0,31,59,90,120,151,181,212,243,273,304,334,365)
        fun f(d: String): Int {
            val m = d.substring(0,2).toInt()
            val dd = d.substring(3,5).toInt()
            return days[m-1] + dd
        }
        val s = maxOf(f(aA), f(aB))
        val e = minOf(f(lA), f(lB))
        return if (s > e) 0 else e - s + 1
    }
}
1
2
3
4
5
6
7
8
9
class Solution:
    def countDaysTogether(self, aA: str, lA: str, aB: str, lB: str) -> int:
        days = [0,31,59,90,120,151,181,212,243,273,304,334,365]
        def f(d: str) -> int:
            m, dd = int(d[:2]), int(d[3:])
            return days[m-1] + dd
        s = max(f(aA), f(aB))
        e = min(f(lA), f(lB))
        return max(0, e - s + 1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
impl Solution {
    pub fn count_days_together(a_a: String, l_a: String, a_b: String, l_b: String) -> i32 {
        let days = [0,31,59,90,120,151,181,212,243,273,304,334,365];
        let f = |d: &str| {
            let m = d[0..2].parse::<usize>().unwrap();
            let dd = d[3..5].parse::<usize>().unwrap();
            days[m-1] + dd
        };
        let s = f(&a_a).max(f(&a_b));
        let e = f(&l_a).min(f(&l_b));
        if s > e { 0 } else { (e - s + 1) as i32 }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution {
    countDaysTogether(aA: string, lA: string, aB: string, lB: string): number {
        const days = [0,31,59,90,120,151,181,212,243,273,304,334,365];
        const f = (d: string) => {
            const m = parseInt(d.slice(0,2)), dd = parseInt(d.slice(3));
            return days[m-1] + dd;
        };
        const s = Math.max(f(aA), f(aB)), e = Math.min(f(lA), f(lB));
        return Math.max(0, e - s + 1);
    }
}

Complexity

  • ⏰ Time complexity: O(1), as all operations are constant time.
  • 🧺 Space complexity: O(1), only a few variables are used.