# Count Days Spent Together
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-days-spent-together)
Canonical: https://scaleengineer.com/dsa/problems/count-days-spent-together
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** String
---
## 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]`.

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

# Approaches
## Simulation using Boolean Arrays
This approach simulates the calendar year and marks the days each person is in Rome. We can use two boolean arrays, one for Alice and one for Bob, of size 366 (to represent days 1 to 365). We first convert the given 'MM-DD' date strings into the corresponding day of the year. Then, we iterate through the date ranges for both Alice and Bob, marking the corresponding days as `true` in their respective arrays. Finally, we iterate through the arrays one more time to count the number of days where both Alice and Bob are present (i.e., both arrays have `true` at the same index).
**Time:** O(N), where N is the number of days in a year (365). The conversion of dates is constant time. The main work involves three loops: one to mark Alice's days, one for Bob's, and one to find common days. In the worst case, these loops run up to N times. Since N is a fixed constant (365), the complexity is technically O(1), but it's less efficient than a direct mathematical calculation. · **Space:** O(N), where N is the number of days in a year. We use two boolean arrays of size 366 to store the presence of Alice and Bob for each day of the year.
**Pros:** The logic is straightforward and easy to follow, as it directly models the problem statement.; It's a robust approach that can be easily adapted if the rules for presence become more complex (e.g., non-contiguous days).
**Cons:** Uses more memory than necessary by creating two large arrays.; The time complexity is proportional to the number of days in the year, which is inefficient compared to a direct calculation.
### Explanation
```java
class Solution {
    public int countDaysSpentTogether(String arriveAlice, String leaveAlice, String arriveBob, String leaveBob) {
        int[] daysInMonth = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        // Create a prefix sum array for quick lookup
        for (int i = 1; i < daysInMonth.length; i++) {
            daysInMonth[i] += daysInMonth[i-1];
        }

        int arriveAliceDay = getDayOfYear(arriveAlice, daysInMonth);
        int leaveAliceDay = getDayOfYear(leaveAlice, daysInMonth);
        int arriveBobDay = getDayOfYear(arriveBob, daysInMonth);
        int leaveBobDay = getDayOfYear(leaveBob, daysInMonth);

        boolean[] alicePresence = new boolean[366];
        boolean[] bobPresence = new boolean[366];

        for (int i = arriveAliceDay; i <= leaveAliceDay; i++) {
            alicePresence[i] = true;
        }
        for (int i = arriveBobDay; i <= leaveBobDay; i++) {
            bobPresence[i] = true;
        }

        int commonDays = 0;
        for (int i = 1; i <= 365; i++) {
            if (alicePresence[i] && bobPresence[i]) {
                commonDays++;
            }
        }
        return commonDays;
    }

    private int getDayOfYear(String date, int[] prefixSum) {
        int month = Integer.parseInt(date.substring(0, 2));
        int day = Integer.parseInt(date.substring(3, 5));
        return prefixSum[month - 1] + day;
    }
}
```
### Algorithm
1.  Define an array `daysInMonth` to store the number of days in each month for a non-leap year: `[31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31]`.
2.  Create a helper function, `getDayOfYear(String date)`, that takes a date string 'MM-DD' and converts it to an integer representing the day of the year (from 1 to 365). This function will parse the month and day, and use the `daysInMonth` array to calculate the total number of days.
3.  In the main function, convert all four input date strings (`arriveAlice`, `leaveAlice`, `arriveBob`, `leaveBob`) into their day-of-the-year integer representations using the helper function.
4.  Initialize two boolean arrays, `alicePresence` and `bobPresence`, of size 366, with all values as `false`.
5.  Iterate from Alice's arrival day to her leave day, setting `alicePresence[day] = true` for each day.
6.  Do the same for Bob, setting `bobPresence[day] = true` for each day he is in Rome.
7.  Initialize a counter `commonDays` to 0.
8.  Iterate from day 1 to 365. If `alicePresence[day]` and `bobPresence[day]` are both `true`, increment `commonDays`.
9.  Return `commonDays`.

## Direct Calculation of Overlapping Interval
A more efficient approach is to treat the problem as finding the length of the intersection of two intervals on a number line. First, we convert all dates into a single, comparable unit: the day of the year (an integer from 1 to 365). Alice's stay is an interval `[startA, endA]` and Bob's is `[startB, endB]`. The period they spend together is the intersection of these two intervals. The start of this intersection is the latest of the two arrival dates, and the end is the earliest of the two departure dates. If the calculated start of the overlap is after the end, it means there is no overlap.
**Time:** O(1). The process involves a fixed number of operations: four date conversions (each constant time), two comparisons (`Math.max`, `Math.min`), and one subtraction. The complexity does not depend on the length of the date intervals. · **Space:** O(1). We only need a few variables to store the calculated day numbers. The array to store the number of days in months has a fixed size (13), which is constant space.
**Pros:** Extremely efficient in both time and space.; The solution is concise and based on a simple mathematical principle.
**Cons:** Requires recognizing the problem as an interval intersection problem, which might be slightly less intuitive than direct simulation.
### Explanation
```java
class Solution {
    public int countDaysSpentTogether(String arriveAlice, String leaveAlice, String arriveBob, String leaveBob) {
        int[] days = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        // Create a prefix sum array for quick lookup
        for (int i = 1; i < days.length; i++) {
            days[i] += days[i-1];
        }

        int arriveAliceDay = getDayOfYear(arriveAlice, days);
        int leaveAliceDay = getDayOfYear(leaveAlice, days);
        int arriveBobDay = getDayOfYear(arriveBob, days);
        int leaveBobDay = getDayOfYear(leaveBob, days);

        int latestArrival = Math.max(arriveAliceDay, arriveBobDay);
        int earliestLeave = Math.min(leaveAliceDay, leaveBobDay);

        int overlap = earliestLeave - latestArrival + 1;

        return Math.max(0, overlap);
    }

    private int getDayOfYear(String date, int[] prefixSum) {
        int month = Integer.parseInt(date.substring(0, 2));
        int day = Integer.parseInt(date.substring(3, 5));
        return prefixSum[month - 1] + day;
    }
}
```
### Algorithm
1.  Define a helper function or use a precomputed array to convert 'MM-DD' date strings into the day of the year (an integer from 1 to 365). A common way is to use a prefix sum array of the number of days in each month.
2.  Convert the four input dates into four integers: `aliceArrivalDay`, `aliceLeaveDay`, `bobArrivalDay`, `bobLeaveDay`.
3.  Determine the start of the overlapping period by finding the maximum of the two arrival days: `startOfOverlap = Math.max(aliceArrivalDay, bobArrivalDay)`.
4.  Determine the end of the overlapping period by finding the minimum of the two leave days: `endOfOverlap = Math.min(aliceLeaveDay, bobLeaveDay)`.
5.  Calculate the duration of the overlap. The number of days is `endOfOverlap - startOfOverlap + 1`.
6.  If `startOfOverlap` is greater than `endOfOverlap`, the intervals do not overlap, and the number of common days is 0. This can be handled by taking `Math.max(0, duration)`.
7.  Return the calculated number of days.

# Solutions
### Java

```java
class Solution {
private
  int[] days = new int[]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
public
  int countDaysTogether(String arriveAlice, String leaveAlice, String arriveBob,
                        String leaveBob) {
    String a = arriveAlice.compareTo(arriveBob) < 0 ? arriveBob : arriveAlice;
    String b = leaveAlice.compareTo(leaveBob) < 0 ? leaveAlice : leaveBob;
    int x = f(a), y = f(b);
    return Math.max(y - x + 1, 0);
  }
private
  int f(String s) {
    int i = Integer.parseInt(s.substring(0, 2)) - 1;
    int res = 0;
    for (int j = 0; j < i; ++j) {
      res += days[j];
    }
    res += Integer.parseInt(s.substring(3));
    return res;
  }
}

```

### Python

```python
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)

```

### CPP

```cpp
class Solution {
public:
  vector<int> days = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
  int countDaysTogether(string arriveAlice, string leaveAlice, string arriveBob,
                        string leaveBob) {
    string a = arriveAlice < arriveBob ? arriveBob : arriveAlice;
    string b = leaveAlice < leaveBob ? leaveAlice : leaveBob;
    int x = f(a), y = f(b);
    return max(0, y - x + 1);
  }
  int f(string s) {
    int m, d;
    sscanf(s.c_str(), "%d-%d", &m, &d);
    int res = 0;
    for (int i = 0; i < m - 1; ++i) {
      res += days[i];
    }
    res += d;
    return res;
  }
};

```