Meeting Room Problems
all meetings problems on leetcode
Meeting Room
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
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
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
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.
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
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
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)