Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Picking the shortest or the earliest-starting meeting can both go wrong.
  2. 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);
    }
}

Solve N Meetings in One Room online · All practice problems