~/leetcode $ 3169. Count-Days-Without-Meetings

Definitely did not just copy the idea straight off ericzheng.nz for this one. I’m not that lazy. I swear. Well, I’m technically not as well versed in the language of algorithms compared to the goat Eric Zheng (also, I can’t program in cpp), but I shall still try nonetheless. I wanted to keep track of these kind of things so that I can articulate my thoughts when solving leetcode questions anyway so its a nice challenge :D.

My initial thoughts after reading this question was to go for something related to interval scheduling and just see where the gaps within schedules are. Then I realized I’m being goofy and that the only information that we need to keep track of is the end time of the current last meeting.

We can iterate through the sorted times of meetings (sorted by start time) and we can check the following:

• if the start time is later than the current end time, an employee is free for the time between the start time and the current end time, so we add that to the result
• if it is not, we can just update the current end time to the new end time if it is later than the current end time

Once we finish iterating through all the meetings, we can add the remaining days to the result as well. We return the result and we finished :D

Code:

class Solution(object):
    def countDays(self, days, meetings):
        """
        :type days: int
        :type meetings: List[List[int]]
        :rtype: int
        """
        res = 0
        curr_end = 0
        
        meetings.sort() 
        for start, end in meetings:
            if start > curr_end:
                res += start - curr_end - 1

            if end > curr_end:
                curr_end = end

        res += days - curr_end
        
        return res

Complexity Analysis:

Time Complexity: O(n log n)

Space Complexity: O(1)