2.1.5. Meeting Room

Meeting room algorithm is a simple algorithm to solve interval questions.

2.1.5.1. Meeting Rooms

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],…] (si < ei), find the minimum number of conference rooms required.

For example, Given [[0, 30],[5, 10],[15, 20]], return 2.

For the example above, we can get the conference room number required with the time line as below:

  1.    2.    1.      2.      1.             0
a.  b.  b/done.  c.     c/done.        a/done
0___5____10______15______20_____________30________________

struct Solution { // T:O(N)
    int minMeetingRooms(vector<Interval>& ivs) {
        vector<pair<int, bool>> vpr;
        for(Interval& e: ivs)
          vpr.emplace_back(e.start, true), vpr.emplace_back(e.end, false);
        // when pr.first equals, for pr.second, false first!
        sort(vpr.begin(), vpr.end());
        int c=0, r=0;
        for(auto& [val, is_start]: vpr){
            if (is_start) ++c; else --c;
            r=max(r,c);
        }
        return r;
    }
};

  • 👽 Adding Meeting Room

Given a list of intervals calendar and a number of available conference rooms. For each query, return true if the meeting can be added to the calendar successfully without causing a conflict, otherwise false. A conference room can only hold one meeting at a time.

Example 1:
Input: calendar = [[1, 2], [4, 5], [8, 10]], rooms = 1, queries = [[2, 3], [3, 4]]
Output: [true, true]

Example 2:
Input: calendar = [[1, 2], [4, 5], [8, 10]], rooms = 1, queries = [[4, 5], [5, 6]]
Output: [false, true]

Example 3:
Input:  calendar = [[1, 3], [4, 6], [6, 8], [9, 11], [6, 9], [1, 3], [4, 10]], rooms = 3, queries = [[1, 9], [2, 6], [7, 9], [3, 5], [3, 9], [2, 4], [7, 10], [5, 9], [3, 10], [9, 10]]
Output: [false, true, false, true, false, true, false, false, false, true]

2.1.5.2. Partition Labels

A string S of lowercase letters is given. We want to partition this string into as many parts as possible so that each letter appears in at most one part, and return a list of integers representing the size of these parts.

Example:
Input: S = "ababcbacadefegdehijhklij"
Output: [9,7,8]
Explanation:
The partition is "ababcbaca", "defegde", "hijhklij".
This is a partition so that each letter appears in at most one part. A partition like "ababcbacadefegde", "hijhklij" is incorrect, because it splits S into less parts.

This problem gives us a string S, and we need to split it into as many substrings as possible, provided that each character can only appear in at most one substring.In the above example, there are multiple a in the string S, and these a appear only in the first substring. All the letter e ​​appear in the second substring. So the difficulty of this question is how to find the partition-points of the string, which is the position where it is split into substrings.

This is the same as meeting room question. Given all meeting time interval and find the time when there is no meeting. But due to the structure of this problem, it can be solved in a even simpler way.

class Solution {
public:
    vector<int> partitionLabels(string S) {
        vector<int> res;
        int n = S.size(), start = 0, last = 0;
        unordered_map<char, int> m;
        for (int i = 0; i < n; ++i) m[S[i]] = i;
        for (int i = 0; i < n; ++i) {
            last = max(last, m[S[i]]);
            if (i == last) {
                res.push_back(i - start + 1);
                start = i + 1;
            }
        }
        return res;
    }
};