Meeting Room Problems

all meetings problems on leetcode

Meeting Room

• Meeting Rooms

Given an array of meeting time intervals where intervals[i] = [starti, endi], determine if a person could attend all meetings.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: false

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: true

Constraints:

• 0 <= intervals.length <= 104
• intervals[i].length == 2
• 0 <= starti < endi <= 106

class Solution {
public:
    bool canAttendMeetings(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return true;
        }
        
        // sort all intervals by their start time.
        sort(intervals.begin(), intervals.end());
        
        for (int i = 1; i < intervals.size(); i++) {
            auto curMeeting = intervals[i];
            auto lastMeeting = intervals[i - 1];
            
            if (curMeeting[0] < lastMeeting[1]) {
                return false;
            }
        }
        return true;
    }
};

Complexity

TC: O(NlgN)

SC: O(1)

Meeting Rooms II

• Meeting Rooms II

Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2

Example 2:

Input: intervals = [[7,10],[2,4]]
Output: 1

Constraints:

• 1 <= intervals.length <= 104
• 0 <= starti < endi <= 106

Image

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        if (intervals.empty()) {
            return 0;
        }
        
         // m.key is timestamp, since map can keep all keys sorted, which is the nature of time.
        map<int, int> m;
        for (const auto &interval: intervals) {
            m[interval[0]]++;
            m[interval[1]]--;
        }
        
        int maxRooms = 0;
        int rooms = 0;
        for (const auto &p: m) {
            rooms += p.second;
            maxRooms = max(maxRooms, rooms);
        }
        
        return maxRooms;
    }
};

The Second approach is that we can use additional heap to simulate the time elapse.

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        // all meetings are sorted by their start time.        
        sort(intervals.begin(), intervals.end());

        // top meeting on heap will end earlier.
        auto cmp = [](const vector<int> &meeting1, const vector<int> &meeting2) {
            return meeting1[1] > meeting2[1];
        };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);
        
        for (const auto& meeting: intervals) {
            // if there's meeting end before current meeting, we could reuse the room later.
            while(!pq.empty() && pq.top()[1] <= meeting[0]) {
                pq.pop();
            }            
            pq.push(meeting);      
        }
      
        // meetings in heap will be the count of rooms
        return pq.size();
    }
};

Car Pooling

• Car Pooling

There is a car with capacity empty seats. The vehicle only drives east (i.e., it cannot turn around and drive west).

You are given the integer capacity and an array trips where trips[i] = [numPassengersi, fromi, toi] indicates that the ith trip has numPassengersi passengers and the locations to pick them up and drop them off are fromi and toi respectively. The locations are given as the number of kilometers due east from the car's initial location.

Return true if it is possible to pick up and drop off all passengers for all the given trips, or false otherwise.

Example 1:

Input: trips = [[2,1,5],[3,3,7]], capacity = 4
Output: false

Example 2:

Input: trips = [[2,1,5],[3,3,7]], capacity = 5
Output: true

Constraints:

• 1 <= trips.length <= 1000
• trips[i].length == 3
• 1 <= numPassengersi <= 100
• 0 <= fromi < toi <= 1000
• 1 <= capacity <= 105

This problem is similar to previous one — meeting room 2, the difference is that we care passengers instead of meeting itself.

Image.png

Use map

class Solution {
    
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        if (trips.empty()) {
            return true;
        }
        
        // key: time, value: passengers_diff
        map<int, int> time;
        for (const auto &trip: trips) {
            time[trip[1]] += trip[0];
            time[trip[2]] -= trip[0];
        }
        
        int cur = 0;
        for (const auto& p: time) {
            cur += p.second;
            if (cur > capacity) {
                return false;
            }
        }        
        
        return true;
    }
};

Complexity

TC: O(NlgN)

SC: O(N)

Use Heap

class Solution {
public:
    bool carPooling(vector<vector<int>>& trips, int capacity) {
        if (trips.empty()) {
            return false;
        }
        if (capacity <= 0) {
            return false;
        }
        
        // sort all trips by their start.
        sort(trips.begin(), trips.end(), [](const vector<int> &t1, const vector<int> &t2){
            return t1[1] < t2[1];
        });
        
        // then we use a heap to get the meetings currently in progress
        auto cmp = [](const vector<int> &t1, const vector<int> &t2) {
            return t1[2] > t2[2];
        };
        priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);
        
        int passengers = 0;
        for (const auto &trip: trips) {
            // we remove all trips before current trip's start
            while(!pq.empty() && pq.top()[2] <= trip[1]) {
                passengers -= pq.top()[0];
                pq.pop();
            }                       
            pq.push(trip);          
          
            passengers += trip[0];
            
            if (passengers > capacity) {
                return false;
            }
        }
        
        return true;
    }
};

Complexity

TC: O(N*lgN)

SC: O(N)

Meeting Scheduler

• Meeting Scheduler

Given the availability time slots arrays slots1 and slots2 of two people and a meeting duration duration, return the earliest time slot that works for both of them and is of duration duration.

If there is no common time slot that satisfies the requirements, return an empty array.

The format of a time slot is an array of two elements [start, end] representing an inclusive time range from start to end.

It is guaranteed that no two availability slots of the same person intersect with each other. That is, for any two time slots [start1, end1] and [start2, end2] of the same person, either start1 > end2 or start2 > end1.

Example 1:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
Output: [60,68]

Example 2:

Input: slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
Output: []

Constraints:

• 1 <= slots1.length, slots2.length <= 104
• slots1[i].length, slots2[i].length == 2
• slots1[i][0] < slots1[i][1]
• slots2[i][0] < slots2[i][1]
• 0 <= slots1[i][j], slots2[i][j] <= 109
• 1 <= duration <= 106

Image.png

Actually, the problem is different from problems above. I’d like to solve the problem here since it all related with meeting. 😄

For this problem, what we need to do is to find overlapped interval between two people and check the length of interval is greater or equal to duration problem requires.

Like the Meeting Room 1, finding overlapped meetings, we can compare end of last meeting with the start time of current meeting, we can use two pointers, one for meeting slots 1 , one for meeting slots 2.

class Solution {
public:
    vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
        // sort all intervals by their start time.
        sort(slots1.begin(), slots1.end());
        sort(slots2.begin(), slots2.end());
        // pointers to interval1 and interval2
        int p1 = 0, p2 = 0;
        while(p1 < slots1.size() && p2 < slots2.size()) {         
            /*
            slot1:     [begin ......... end] 
            slot2: [begin ....... end]
            */
            // check intersection
            int left = max(slots1[p1][0], slots2[p2][0]);
            int right = min(slots1[p1][1], slots2[p2][1]);
            if (left < right && right - left >= duration) {
                return {left, left + duration};
            }
            
            // move the time slot end first
            if (slots1[p1][1] < slots2[p2][1]) {
                p1++;
            } else {
                p2++;
            }
        }        
        return {};
    }
};

Complexity

TC: O(MlgM + NlgN)

SC: O(1)

We should remember the fact the problem describes.

It is guaranteed that no two availability slots of the same person intersect with each other.

So, we can handle all intervals in one dimension.

class Solution {
public:
    vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
        vector<vector<int>> slots;
        for (const auto& s: slots1) {
            if (s[1] - s[0] >= duration) {
                slots.push_back(s);
            }
        }
        for (const auto& s: slots2) {
            if (s[1] - s[0] >= duration) {
                slots.push_back(s);
            }
        }
                
        sort(slots.begin(), slots.end());
        
        for (int i = 1; i < slots.size(); i++) {
            auto last = slots[i - 1];
            auto current = slots[i];
            
            int left = max(last[0], current[0]);
            int right = min(last[1], current[1]);
            if (right - left >= duration) {
                return {left, left+duration};
            }
        }
        
        return {};
    }
};

Complexity

TC: O((M+N)lg(M+N))

SC: O(M+N)