Practice › Greedy
N Meetings in One Room
Medium · Greedy · Asked at Amazon, Microsoft, Flipkart, Paytm
Meeting i runs from start[i] to end[i]. A meeting can only begin strictly after the previous one ends. Print the maximum number of meetings that fit in one room.
Input
Line 1: n. Line 2: n start times. Line 3: n end times.
Output
The maximum number of meetings.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ start < end ≤ 10^9
Sort by end time and always pick the meeting that finishes earliest.
Example 1
Input
6 1 3 0 5 8 5 2 4 6 7 9 9
Output
4
Example 2
Input
3 10 12 20 20 25 30
Output
1
Hints
- Picking the shortest or the earliest-starting meeting can both go wrong.
- Sort by end time and always take the next meeting that starts strictly after the last chosen one ends.
Approach
Activity selection. Sort meetings by end time. Take a meeting whenever its start > lastEnd (strictly, as required here), and set lastEnd to its end. Finishing as early as possible leaves the most time for the rest. The exchange argument: any optimal schedule can swap its first meeting for the earliest-ending one without losing anything.
Complexity: O(n log n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<pair<long long, long long>> mt(n); // (end, start)
for (auto &p : mt) cin >> p.second;
for (auto &p : mt) cin >> p.first;
sort(mt.begin(), mt.end());
int count = 0;
long long lastEnd = -1;
for (auto &p : mt)
if (p.second > lastEnd) {
count++;
lastEnd = p.first;
}
cout << count << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
starts = data[1 : n + 1]
ends = data[n + 1 : 2 * n + 1]
count, last_end = 0, -1
for end, start in sorted(zip(ends, starts)):
if start > last_end:
count += 1
last_end = end
print(count)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[][] mt = new long[n][2]; // {start, end}
for (int i = 0; i < n; i++) mt[i][0] = sc.nextLong();
for (int i = 0; i < n; i++) mt[i][1] = sc.nextLong();
Arrays.sort(mt, (x, y) -> Long.compare(x[1], y[1]));
int count = 0;
long lastEnd = -1;
for (long[] m : mt)
if (m[0] > lastEnd) {
count++;
lastEnd = m[1];
}
System.out.println(count);
}
}