Teaching Kids Programming – Count Days Spent Together (Intersection of Two Intervals + Line Sweep Algorithm)

Teaching Kids Programming: Videos on Data Structures and Algorithms

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.

Both alice and bob arrives and leaves at the same calendar year, and thus we can easily convert the dates to the number of days since 1/Jan. Then this problem can be transformed into the intesection of two intervals.

Intersection of Two Intervals

Assuming this is a non-leap year, so the Feburary has 28 days. We need a function to convert the date string in the format of “MM-DD” such as “01-02” to a integer [1, 365], the number of days since 1/Jan. We need to declare the number of days in each month respectively.

1
2
3
4
5
6

# here we have a padding zero at the start because the month starts 1.
days = (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)
 
def f(date):
    month, day = map(int, date.split("-"))
    return sum(days[:month]) + day

# here we have a padding zero at the start because the month starts 1.
days = (0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31)

def f(date):
    month, day = map(int, date.split("-"))
    return sum(days[:month]) + day

Then, we need to rule out the two cases when there are no intersections of both intervals. Otherwise, we unify the four cases of intersections – by getting the smaller of right ends, and the larger of the left ends.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution:
    def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
        alice_1 = f(arriveAlice)
        alice_2 = f(leaveAlice)
 
        bob_1 = f(arriveBob)
        bob_2 = f(leaveBob)
 
        if alice_2 < bob_1 or alice_1 > bob_2:
            return 0
 
        return abs(min(alice_2, bob_2) - max(alice_1, bob_1)) + 1

class Solution:
    def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
        alice_1 = f(arriveAlice)
        alice_2 = f(leaveAlice)

        bob_1 = f(arriveBob)
        bob_2 = f(leaveBob)

        if alice_2 < bob_1 or alice_1 > bob_2:
            return 0

        return abs(min(alice_2, bob_2) - max(alice_1, bob_1)) + 1

The time/space complexity is O(1) constant as the problem is bounded to 12 months + 365 days.

Line Sweeping Algorithm (Prefix Sum) + Two Intervals Intersection

We can apply the Line Sweeping Algorithm to find the intersections of two intervals. There are 365 days, and we need to allocate 367 buckets/counters because index at zero is not used (day start at 1), and there are 365 days (from day 1 to day 365). Also, we need to mark the next day of departure minus one – thus requiring access to day 366.

After we mark two arrival days and two departure days, we can conduct the line sweeping from left to right (starting from day 1 and finish at day 366). We accumulate the sum, and increment the answer when the sum is two.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution:
    def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
        arr = [0] * 367
        arr[f(arriveAlice)] += 1
        arr[f(leaveAlice) + 1] -= 1
 
        arr[f(arriveBob)] += 1
        arr[f(leaveBob) + 1] -= 1
 
        ans = 0
        x = 0
        for i in range(len(arr)):
            x += arr[i]
            if x == 2:
                ans += 1
        return ans

class Solution:
    def countDaysTogether(self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str) -> int:
        arr = [0] * 367
        arr[f(arriveAlice)] += 1
        arr[f(leaveAlice) + 1] -= 1

        arr[f(arriveBob)] += 1
        arr[f(leaveBob) + 1] -= 1

        ans = 0
        x = 0
        for i in range(len(arr)):
            x += arr[i]
            if x == 2:
                ans += 1
        return ans

The python’s function accumulate returns an iterator to the prefix sum, and then we convert it to list, and count how many of them are two which indicates the overlapping of two intervals:

1
2

s = list(accumulate(arr))
return s.count(2)

s = list(accumulate(arr))
return s.count(2)

O(1) time/space complexity as the problem is bounded.

–EOF (The Ultimate Computing & Technology Blog) —