Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/2409.html
2409. Count Days Spent Together
- Difficulty: Easy.
- Related Topics: .
- Similar Questions: Number of Days Between Two Dates, Minimum Number of Operations to Convert Time.
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.
Solution (Java, C++, Python)
-
class Solution { int[] months = new int[]{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; public int countDaysTogether(String s1, String e1, String s2, String e2) { int[] a = new int[]{ getVal(s1), getVal(e1) }; int[] b = new int[]{ getVal(s2), getVal(e2) }; if(b[0]>a[1] || a[0]>b[1]) return 0; // no overlap int start = Math.max(a[0], b[0]); int last = Math.min(a[1], b[1]); return last-start+1; } // convert date to nth day of year, (1st-365th day) int getVal(String str){ int idx = 0; int mon = (str.charAt(0)-'0')*10+(str.charAt(1)-'0'); int day = (str.charAt(3)-'0')*10+(str.charAt(4)-'0'); for(int i=1; i<mon; i++) idx += months[i-1]; // or use prefix sum return idx+day; } } ############ 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; } } -
class Solution: def countDaysTogether( self, arriveAlice: str, leaveAlice: str, arriveBob: str, leaveBob: str ) -> int: if leaveAlice < arriveBob or leaveBob < arriveAlice: return 0 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 y - x + 1 ############ # 2409. Count Days Spent Together # https://leetcode.com/problems/count-days-spent-together/ class Solution: def countDaysTogether(self, a: str, b: str, c: str, d: str) -> int: months = [0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31] days = [[0] * (month + 1) for month in months] def go(A, B): a, b = map(int, A.split('-')) c, d = map(int, B.split('-')) if a != c: for month in range(a, c): if month == a: for day in range(b, months[month] + 1): days[month][day] += 1 else: for day in range(months[month] + 1): days[month][day] += 1 for day in range(1, d + 1): days[c][day] += 1 return for day in range(b, d + 1): days[c][day] += 1 res = 0 go(a, b) go(c, d) for month in range(len(months)): for day in range(months[month] + 1): if day == 0: continue if days[month][day] == 2: res += 1 return res -
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; } }; -
func countDaysTogether(arriveAlice string, leaveAlice string, arriveBob string, leaveBob string) int { days := []int{31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} f := func(s string) int { m, _ := strconv.Atoi(s[:2]) d, _ := strconv.Atoi(s[3:]) res := 0 for i := 0; i < m-1; i++ { res += days[i] } res += d return res } a, b := arriveAlice, leaveBob if arriveAlice < arriveBob { a = arriveBob } if leaveAlice < leaveBob { b = leaveAlice } x, y := f(a), f(b) ans := y - x + 1 if ans < 0 { return 0 } return ans }
Explain:
nope.
Complexity:
- Time complexity : O(n).
- Space complexity : O(n).