Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2402.html

2402. Meeting Rooms III

  • Difficulty: Hard.
  • Related Topics: Array, Sorting, Heap (Priority Queue).
  • Similar Questions: Meeting Rooms, Meeting Rooms II, Maximum Number of Events That Can Be Attended, Find Servers That Handled Most Number of Requests, Maximum Number of Events That Can Be Attended II.

Problem

You are given an integer n. There are n rooms numbered from 0 to n - 1.

You are given a 2D integer array meetings where meetings[i] = [starti, endi] means that a meeting will be held during the half-closed time interval [starti, endi). All the values of starti are unique.

Meetings are allocated to rooms in the following manner:

  • Each meeting will take place in the unused room with the lowest number.

  • If there are no available rooms, the meeting will be delayed until a room becomes free. The delayed meeting should have the same duration as the original meeting.

  • When a room becomes unused, meetings that have an earlier original start time should be given the room.

Return** the number of the room that held the most meetings. If there are multiple rooms, return the room with the lowest number.**

A half-closed interval [a, b) is the interval between a and b including a and not including b.

  Example 1:

Input: n = 2, meetings = [[0,10],[1,5],[2,7],[3,4]]
Output: 0
Explanation:
- At time 0, both rooms are not being used. The first meeting starts in room 0.
- At time 1, only room 1 is not being used. The second meeting starts in room 1.
- At time 2, both rooms are being used. The third meeting is delayed.
- At time 3, both rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 1 finishes. The third meeting starts in room 1 for the time period [5,10).
- At time 10, the meetings in both rooms finish. The fourth meeting starts in room 0 for the time period [10,11).
Both rooms 0 and 1 held 2 meetings, so we return 0. 

Example 2:

Input: n = 3, meetings = [[1,20],[2,10],[3,5],[4,9],[6,8]]
Output: 1
Explanation:
- At time 1, all three rooms are not being used. The first meeting starts in room 0.
- At time 2, rooms 1 and 2 are not being used. The second meeting starts in room 1.
- At time 3, only room 2 is not being used. The third meeting starts in room 2.
- At time 4, all three rooms are being used. The fourth meeting is delayed.
- At time 5, the meeting in room 2 finishes. The fourth meeting starts in room 2 for the time period [5,10).
- At time 6, all three rooms are being used. The fifth meeting is delayed.
- At time 10, the meetings in rooms 1 and 2 finish. The fifth meeting starts in room 1 for the time period [10,12).
Room 0 held 1 meeting while rooms 1 and 2 each held 2 meetings, so we return 1. 

  Constraints:

  • 1 <= n <= 100

  • 1 <= meetings.length <= 105

  • meetings[i].length == 2

  • 0 <= starti < endi <= 5 * 105

  • All the values of starti are unique.

Solution (Java, C++, Python)

  • class Solution {
      public int mostBooked(int n, int[][] meetings) {
        int ans[] = new int[n];                                                     //for numbers of usages 
        PriorityQueue<int[]> ends = new PriorityQueue<>
          (n, (int[] o1, int[] o2) -> o2[0]!=o1[0] ? o1[0]-o2[0] : o1[1]-o2[1]);    //end , room   
        TreeSet<Integer> rooms = new TreeSet<>();                                   //for empty rooms
        for(int i = 0; i != n; i++) rooms.add(i);                                   //check all rooms as empty 
        Arrays.sort(meetings, (int[] o1, int[] o2) -> o1[0] - o2[0]);               //sorting for minimal starts
      
        for(int[] m: meetings){
          while(!ends.isEmpty() && ends.peek()[0] <= m[0]) rooms.add(ends.poll()[1]);       //empty all rooms for current time
          
          if(!rooms.isEmpty()){                                          //if we have empty rooms
            int room = rooms.pollFirst();                                //fetch room with minimal number
            ans[room]++;                                                 //check it as used
            ends.add(new int[]{m[1], room});                             //and put it into queue
          }else{                                                     //if we not have any empty room 
            int[] e = ends.poll();                                   //fetch from queue first room that will be empty 
            ans[e[1]]++;                                             //and again use it (check it as used)
            ends.add(new int[]{e[0] + m[1] - m[0], e[1]});           //and reuse it with correct time
          } 
        }
        
        int maxi = 0, id = -1;                          //fetch minimal index from array with numbers of usages
        for(int i = 0; i != n; i++)
          if(ans[i] > maxi) {maxi = ans[i]; id = i;}
        
        return id;
      }
    }
    
    ############
    
    class Solution {
        public int mostBooked(int n, int[][] meetings) {
            Arrays.sort(meetings, (a, b) -> a[0] - b[0]);
            PriorityQueue<int[]> busy
                = new PriorityQueue<>((a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
            PriorityQueue<Integer> idle = new PriorityQueue<>();
            for (int i = 0; i < n; ++i) {
                idle.offer(i);
            }
            int[] cnt = new int[n];
            for (var v : meetings) {
                int s = v[0], e = v[1];
                while (!busy.isEmpty() && busy.peek()[0] <= s) {
                    idle.offer(busy.poll()[1]);
                }
                int i = 0;
                if (!idle.isEmpty()) {
                    i = idle.poll();
                    busy.offer(new int[] {e, i});
                } else {
                    var x = busy.poll();
                    i = x[1];
                    busy.offer(new int[] {x[0] + e - s, i});
                }
                ++cnt[i];
            }
            int ans = 0;
            for (int i = 0; i < n; ++i) {
                if (cnt[ans] < cnt[i]) {
                    ans = i;
                }
            }
            return ans;
        }
    }
    
  • class Solution:
        def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
            meetings.sort()
            busy = []
            idle = list(range(n))
            heapify(idle)
            cnt = [0] * n
            for s, e in meetings:
                while busy and busy[0][0] <= s:
                    heappush(idle, heappop(busy)[1])
                if idle:
                    i = heappop(idle)
                    cnt[i] += 1
                    heappush(busy, (e, i))
                else:
                    a, i = heappop(busy)
                    cnt[i] += 1
                    heappush(busy, (a + e - s, i))
            ans = 0
            for i, v in enumerate(cnt):
                if cnt[ans] < v:
                    ans = i
            return ans
    
    ############
    
    # 2402. Meeting Rooms III
    # https://leetcode.com/problems/meeting-rooms-iii/
    
    class Solution:
        def mostBooked(self, n: int, meetings: List[List[int]]) -> int:
            meetings.sort(key = lambda x: x[0])
            usedCount = [0] * n
            h = []
            freshRooms = []
    
            for roomId in range(n):
                heappush(freshRooms, (0, roomId))
            
            for start, end in meetings:
                temp = []
                
                while h and h[0][0] < start:
                    endTime, roomId = heappop(h)
                    temp.append((start, roomId))
                
                for endTime, roomId in temp:
                    heappush(h, (endTime, roomId))
                
                duration = end - start
    
                if not h or (freshRooms and h and h[0][0] > start):
                    endTime, roomId = heappop(freshRooms)
                else:
                    endTime, roomId = heappop(h)
                    
                usedCount[roomId] += 1
                d = endTime + duration if endTime != 0 else end
                heappush(h, (d, roomId))
    
            maxUsed = max(usedCount)
            
            for roomId, count in enumerate(usedCount):
                if count == maxUsed:
                    return roomId
            
            return -1
    
    
  • using ll = long long;
    using pii = pair<ll, int>;
    
    class Solution {
    public:
        int mostBooked(int n, vector<vector<int>>& meetings) {
            priority_queue<int, vector<int>, greater<int>> idle;
            priority_queue<pii, vector<pii>, greater<pii>> busy;
            for (int i = 0; i < n; ++i) idle.push(i);
            vector<int> cnt(n);
            sort(meetings.begin(), meetings.end());
            for (auto& v : meetings) {
                int s = v[0], e = v[1];
                while (!busy.empty() && busy.top().first <= s) {
                    idle.push(busy.top().second);
                    busy.pop();
                }
                int i = 0;
                if (!idle.empty()) {
                    i = idle.top();
                    idle.pop();
                    busy.push({e, i});
                } else {
                    auto x = busy.top();
                    busy.pop();
                    i = x.second;
                    busy.push({x.first + e - s, i});
                }
                ++cnt[i];
            }
            int ans = 0;
            for (int i = 0; i < n; ++i) {
                if (cnt[ans] < cnt[i]) {
                    ans = i;
                }
            }
            return ans;
        }
    };
    
  • func mostBooked(n int, meetings [][]int) int {
    	sort.Slice(meetings, func(i, j int) bool { return meetings[i][0] < meetings[j][0] })
    	idle := hp{make([]int, n)}
    	for i := 0; i < n; i++ {
    		idle.IntSlice[i] = i
    	}
    	busy := hp2{}
    	cnt := make([]int, n)
    	for _, v := range meetings {
    		s, e := v[0], v[1]
    		for len(busy) > 0 && busy[0].end <= s {
    			heap.Push(&idle, heap.Pop(&busy).(pair).i)
    		}
    		var i int
    		if idle.Len() > 0 {
    			i = heap.Pop(&idle).(int)
    			heap.Push(&busy, pair{e, i})
    		} else {
    			x := heap.Pop(&busy).(pair)
    			i = x.i
    			heap.Push(&busy, pair{x.end + e - s, i})
    		}
    		cnt[i]++
    	}
    	ans := 0
    	for i, v := range cnt {
    		if cnt[ans] < v {
    			ans = i
    		}
    	}
    	return ans
    }
    
    type hp struct{ sort.IntSlice }
    
    func (h *hp) Push(v interface{}) { h.IntSlice = append(h.IntSlice, v.(int)) }
    func (h *hp) Pop() interface{} {
    	a := h.IntSlice
    	v := a[len(a)-1]
    	h.IntSlice = a[:len(a)-1]
    	return v
    }
    
    type pair struct{ end, i int }
    type hp2 []pair
    
    func (h hp2) Len() int { return len(h) }
    func (h hp2) Less(i, j int) bool {
    	a, b := h[i], h[j]
    	return a.end < b.end || a.end == b.end && a.i < b.i
    }
    func (h hp2) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
    func (h *hp2) Push(v interface{}) { *h = append(*h, v.(pair)) }
    func (h *hp2) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
    

Explain:

nope.

Complexity:

  • Time complexity : O(n).
  • Space complexity : O(n).

All Problems

All Solutions