[Java/C++] Clean Code


  • 7

    Summarize
    This is to find the maximum number of concurrent ongoing event at any time.

    We can log the start & end of each event on the timeline, each start add a new ongoing event at that time, each end terminate an ongoing event. Then we can scan the timeline to figure out the maximum number of ongoing event at any time.

    Java

    class MyCalendarThree {
        private TreeMap<Integer, Integer> times = new TreeMap<>();
        public int book(int s, int e) {
            times.put(s, times.getOrDefault(s, 0) + 1); // 1 new event will be starting at times[s]
            times.put(e, times.getOrDefault(e, 0) - 1); // 1 new event will be ending at times[e];
            int ongoing = 0, k = 0;
            for (int v : times.values())
                k = Math.max(k, ongoing += v);
            return k;
        }
    }
    

    C++

    class MyCalendarThree {
        map<int, int> times;
    public:
        int book(int s, int e) {
            times[s]++; // 1 new event will be starting at times[s]
            times[e]--; // 1 new event will be ending at times[e];
            int ongoing = 0, k = 0;
            for (pair<int, int> t : times)
                k = max(k, ongoing += t.second);
            return k;
        }
    };
    
    

  • 1
    W

    Similar idea using Python

    from bisect import insort
    class MyCalendarThree(object):
    
        def __init__(self):
            self.times=[]
    
        def book(self, start, end):
            """
            :type start: int
            :type end: int
            :rtype: int
            """
            insort(self.times,(start,1))
            insort(self.times,(end,-1))
    
            res=cumsum=0
            for _,x in self.times:
                cumsum+=x
                res=max(res,cumsum)
            return res
    

  • 0

    Good job! Upvoted! I think this method also could be applied to Meeting Rooms II.
    I got the easiest version for Meeting Rooms II below:

    class Solution {
        public int minMeetingRooms(Interval[] intervals) {
            if (intervals == null || intervals.length == 0) {
                return 0;
            }
            
            TreeMap<Integer, Integer> times = new TreeMap<>();
            for (Interval i : intervals) {
                times.put(i.start, times.getOrDefault(i.start, 0) + 1);
                times.put(i.end, times.getOrDefault(i.end, 0) - 1);
            }
            
            int count = 0, res = 0;
            for (int c : times.values()) {
                count += c;
                res = Math.max(res, count);
            }
            
            return res;
        }
    }
    

  • 0
    L

    @weidairpi
    Thank you for sharing. Clean and simple.


  • 0

    @alexander Thanks for the clean solution. But I think the loop for (pair<int, int> t : times) does not need to re-compute time stamps outside of window [s, e). I re-wrote the solution a little here as a data structure design problem.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.