FastPrep
Problem · Intervals

Minimum Number of Chairs

Learn this problem
● EasyGoogleOA
See Google hiring insights

Problem statement

There are n guests who are invited to a party. The k-th guest will attend the party at time S[k] and leave the party at time E[k].

Given an integer array S and an integer array E, both of length n, return an integer denoting the minimum number of chairs you need such that everyone attending the party can sit down.

Function

minChairs(S: int[], E: int[]) → int

Complete the function minChairs in the editor.

minChairs has the following parameters:

  1. int S[n]: an array of integers representing the arrival times
  2. int E[n]: an array of integers representing the leaving times

Returns

int: the minimum number of chairs needed

Examples

Example 1

S = [1, 2, 6, 5, 3]E = [5, 5, 7, 6, 8]return = 3
There are five guests attending the party.
  • The 1st guest will arrive at time 1. We need one chair at time 1.
  • The 2nd guest will arrive at time 2. There are now two guests at the party, so we need two chairs at time 2.
  • The 5th guest will arrive at time 3. There are now three guests at the party, so we need three chairs at time 3.
  • The 4th guest will arrive at time 5 and, at the same moment, the 1st and 2nd guests will leave the party.
  • There are now two (the 4th and 5th) guests at the party, so we need two chairs at time 5.
  • The 3rd guest will arrive at time 6, and the 4th guest will leave the party at the same time.
  • There are now two (the 3rd and 5th) guests at the party, so we need two chairs at time 6.
    • So we need at least 3 chairs.

    Constraints

    • 1 ≤ S.length = E.length ≤ 2 * 10^5
    • S[i] < E[i] for every guest.
    • Attendance intervals are half-open: a guest leaving at time t frees a chair for a guest arriving at time t.
    • All times are integers in [-10^9, 10^9].

    More Google problems

    drafts saved locally
    public int minChairs(int[] S, int[] E) {
    // write your code here
}
    S[1, 2, 6, 5, 3]
    E[5, 5, 7, 6, 8]
    expected3
    checking account