Explanation of "Super Easy Java Solution Beats 98.8%" from @pinkfloyda


  • 123
    M

    The solution is proposed by @pinkfloyda at "Super Easy Java Solution Beats 98.8%" , which is amazing.

    Here I would like to explain why it works a little bit.

    The code from @pinkfloyda:

    public class Solution {
        public int minMeetingRooms(Interval[] intervals) {
            int[] starts = new int[intervals.length];
            int[] ends = new int[intervals.length];
            for(int i=0; i<intervals.length; i++) {
                starts[i] = intervals[i].start;
                ends[i] = intervals[i].end;
            }
            Arrays.sort(starts);
            Arrays.sort(ends);
            int rooms = 0;
            int endsItr = 0;
            for(int i=0; i<starts.length; i++) {
                if(starts[i]<ends[endsItr])
                    rooms++;
                else
                    endsItr++;
            }
            return rooms;
        }
    }
    

    To understand why it works, first let’s define two events:
    Meeting Starts
    Meeting Ends

    Next, we acknowledge three facts:
    The numbers of the intervals give chronological orders
    When an ending event occurs, there must be a starting event has happened before that, where “happen before” is defined by the chronological orders given by the intervals
    Meetings that started which haven’t ended yet have to be put into different meeting rooms, and the number of rooms needed is the number of such meetings

    So, what this algorithm works as follows:

    for example, we have meetings that span along time as follows:

    |_____|
          |______|
    |________|
            |_______|
    

    Then, the start time array and end time array after sorting appear like follows:

    ||    ||
         |   |   |  |
    

    Initially, endsItr points to the first end event, and we move i which is the start event pointer. As we examine the start events, we’ll find the first two start events happen before the end event that endsItr points to, so we need two rooms (we magically created two rooms), as shown by the variable rooms. Then, as i points to the third start event, we’ll find that this event happens after the end event pointed by endsItr, then we increment endsItr so that it points to the next end event. What happens here can be thought of as one of the two previous meetings ended, and we moved the newly started meeting into that vacant room, thus we don’t need to increment rooms at this time and move both of the pointers forward.
    Next, because endsItr moves to the next end event, we’ll find that the start event pointed by i happens before the end event pointed by endsItr. Thus, now we have 4 meetings started but only one ended, so we need one more room. And it goes on as this.


  • 0

    This is greater than my add & release room algorithm


  • 0
    J

    It seems that this method is same as the min priority queue, right?


  • 0
    M

    If you mean time as the priority, then I guess so.


  • 0
    B

    this is amazingly clear!


  • 28
    O

    Thanks for @magicyuli 's effort. But I didn't fully understand. I shall share a bit of my thought:

    In https://leetcode.com/discuss/50911/ac-java-solution-using-min-heap, if solution by @jeantimex is the greatest and clearest, solution by @pinkfloyda is crazy. I really spent a lot time and thought about why he can use such a solution.

    To understand the solution, we need first understand the mindset from @jeantimex. That is, for example you are the meeting manager, there are 3 room having meeting, room A ends at 5, room B ends at 7, room C ends at 9: if there’s a meeting [6,11] to be arranged, you will put it in room A because A ends before this meeting, then your meeting schedule updates as: room A ends at 11, B at 7, C at 9; if there’s a meeting [4, 11] to be arranged, you have no way but to add another room D, then your meeting schedule updates as: roomA ends at 5, B at 7, C at 9, D at 11. So the mindset is sort the meetings by start time. Iterate through the meetings, add each meeting in the room that finishes earliest, if not possible, put it in a new room.

    In this solution, we sort the meetings by start time as start list to have the same iteration sequence. We sort the meetings by end time to end list so that it makes sure each elements represents the meeting that ends earliest in its room compared to other meeting that are behind it in the end list. Take an example:

    [2,3],[0,4],[6,7],[0,9][5,8]

    so the start and end lists are:

    st: 0, 0, 2, 4, 5

    ed: 3, 4, 7, 8, 9

    Suppose i is the index of st list, which is the start time of meeting you want to add in to the schedule. Suppose firstEnd is the index of ed list, which is the first end time of in your meeting rooms.
    You first add a meeting that finishes earliest in a room. But wait, you may ask, what meeting are you talking about? what about the start time of the meeing? You have saperated start and end time of a meeting so that meeting is lost! Damn, I had the same confusion too. First imagine that you know which meeting it is, so, for the first meeting that finishes the earliest, you iterate throught the meeting in the start list, you see: @ i = 0, this meeting starts at 0, before the earliest-end meeting (which is pointed by index firstEnd, which ends at time 3), what do you do? You can do nothing else but to add another room, room B. When does room B finishes? It finishes at a time that is behind index firstEnd in the end list. Which one? I don’t know. But the only thing I know is the earlist meeting that finishes is at 3. You then increase i = 1, you see it starts 0, before the earliest-end meeting. Even the learliest-end meeting finishes after this meeting, so you have no way to use a existing room for it because it will have time collision. So as long as you have a meeting whose start time is earlier than the earliest-end meeting finish time, you add a room, room C. Then you go to i = 2, which finishes at 2 < 3 (pointed by firstEnd in end list), add a room, room A. Why room A? I just want to give it a name A ok? Alright, you remember you don’t know the meeting which ends the earliest, know you encounter it, actually, this room A is the first room that provides the meeting room for the earliest-end meeting. You see this whole process happens silently and internally. Hence, up to i=2, you added three room, and you know the earliest-end meeting finishes at 3. Before you encouter a meeting that starts no earlier than earliest-end meeting, you must have encountered the earliest-end meeting’s start time and silently put that meeting in one of the room you added.

    You then increase i=3, found start time = 4 which is no earlier than earliest-end meeting. Now your time is 4, you have passed the earliest-end meeting, so you increase the firstEnd index to find the next earliest-end meeting among all rooms, which ends at 4. And you now found you can put this meeting right after this earliest-end meeting with no need to add new room. And then you update firstEnd=3 and go to i=5 and found the next meeting starts earlier than all the meeings among the existing rooms, you add a room.

    Hope is helps. Below is my code, 4ms 99.5%.

    public class Solution {
        public int minMeetingRooms(Interval[] l) {
            int n = l.length, i = 0, firstEnd = 0;
            int[] st = new int[n], ed = new int[n];
            for (int j = 0; j < n; st[j] = l[j].start, ed[j] = l[j].end, j++);
            Arrays.sort(st);
            Arrays.sort(ed);
            for (; i < n; i++)
                if (st[i] >= ed[firstEnd]) firstEnd++;
            return i - firstEnd;
        }
    }
    

  • 0
    This post is deleted!

  • 0
    M

    Really nice and detailed explanation! Thank you !


  • 0
    C

    How is this solution correct? Isn't min num of rooms in your example 3?
    [2,3],[5,8] can happen in same room
    [0,4],[6,7] same room
    [0,9]

    While your solution gives 4.


  • 0
    C

    please ignore - solution works fine!


  • 1
    R

    I think the premise of this solution is counting the number of overlapping intervals. If you think about it, any overlapping interval => room conflict. pinkfloyda's solution is a modification of max # of overlapping intervals.


  • 19

    Here is my thought. whenever there is a start meeting, we need to add one room. But before adding rooms, we check to see if any previous meeting ends, which is why we check start with the first end. When the start is bigger than end, it means at this time one of the previous meeting ends, and it can take and reuse that room. Then the next meeting need to compare with the second end because the first end's room is already taken. One thing is also good to know: meetings start is always smaller than end. Whenever we pass a end, one room is released.

        public int minMeetingRooms(Interval[] intervals) {
            if (intervals == null || intervals.length == 0) return 0;
            int n = intervals.length, index = 0;
            int[] begins = new int[n];
            int[] ends = new int[n];
            for (Interval i: intervals) {
                begins[index] = i.start;
                ends[index] = i.end;
                index++;
            }
            Arrays.sort(begins);
            Arrays.sort(ends);
            int rooms = 0, pre = 0;
            for (int i = 0; i < n; i++) {
                rooms++;
                if (begins[i] >= ends[pre]) {
                    rooms--;
                    pre++;
                }
            }
            return rooms;
        }
    

  • 0
    O

    @alanwang very nice elaboration!


  • 0

    Thanks for your explain.


  • 0
    A

    It's pretty intuitive after understanding the onset.
    More start than finished meetings, meaning more rooms will be needed. More meetings popping up during other meetings/while other rooms are in use, so new rooms need to be added to accommodate. Very real world scenario.


  • 0
    D

    Inspired by event based thinking,

    var minMeetingRooms = function(intervals) {
        let events = [];
        for (let i of intervals) {
            events.push({val: i.start, type: 1});
            events.push({val: i.end, type: 0});
        }
        events.sort((a,b)=> a.val==b.val? a.type-b.type: a.val-b.val);
        let rooms = 0;
        let max = 0;
        for (let ev of events) {
            if (ev.type===1) {
                rooms ++;
                max = Math.max(max, rooms);
            } else {
                rooms --;
            }
        }
        return max;
    };
    

  • 0
    M
    This post is deleted!

  • 1
    H

    Thanks @magicyuli !! Let me expand the graph,

    +----------------------> new room #1 for meeting "a"
    |+---------------------> no meeting finish, new room #2 for meeting "b"
    ||    +----------------> one meeting finished at time "w", maybe #1, maybe #2, not important!
    ||    |                           meeting "c" use this old room.
    ||    |+---------------> no more meeting finish, new room #2 for meeting "b"
    ab    cd
    ||    ||                <- start time (4 meetings begun at time a,b,c,d)
         |   |   |  |       <- end time (they finished at w,x,y,z, order not important)
         w   x   y  z
    

  • 0
    L

    @alanwang I think this is actually the best explanation for the algorithm.


  • 0

    @alanwang i love your explanation. Most easiest one to understand


Log in to reply
 

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