Meeting Rooms | InterviewBit | Solution Explained

I explain the solution to Meeting Rooms on InterviewBit using visuals in simple words.

0. Meeting Rooms: Problem Discussion

0.0. IO Format

  • input:
    • a list of intervals, where each interval is given by [s,e] which are the start and the end times of the intervals
  • output:
    • find the least number of meeting rooms required to conduct all the meetings
  • constraints:
    • 1 <= N <= 1e5
    • 1 <= s <= e <= 1e9

0.1. Examples

Meeting Rooms: sample test case
Meeting Rooms: sample test case

Visually speaking, we can see that the maximum number of meeting rooms we require is 2, at two different places of times.

1. Meeting Rooms: Observations & Logic

1.0. Naïve

The naïve approach suggests that we can go over all the times one by one, and check the number of meetings going on at each point of time.

That is, for each time = t, we go over all the N elements to find the count of meetings going on simultaneously.

Meeting Rooms: test case giving TLE
Meeting Rooms: test case giving TLE

The only issue is that the time complexity become O(TN), and according to the constraints of the problem, that is a sure fire Time Limit Exceeded (TLE).

All right, so what do we do instead?

1.1. Only important times matter

Meeting Rooms: test case explanation for optimization
Meeting Rooms: test case explanation for optimization

The key is to realize, looking at the example shown above, is that most of the time, the number of meeting rooms is not going to change.

What I mean is that for times 0, 1, 2, 3, 4, the number of meeting rooms do not change. Then, at time = 5, the number of required meeting rooms becomes 2.

But, then again, the required rooms stays at 2 for t = 6, 7, 8, 9.

All this means is that we are doing a lot of useless computation. Thus, the realization, only the important times matter – when there is a change.

1.2. Changing times

To formalize, we want to look at what happens for each start time, s, and what happens to each end time, e.

At each start time, for any interval, the number of required meeting rooms increase by 1. Similarly, for each end time, for all intervals, the required rooms decreases by 1.

Meeting Rooms: Change in rooms required logic
Meeting Rooms: Change in rooms required logic

The only thing left to do is to look at this in terms of code. We do two things:

  • convert these t: change values to a tuple, (t, change) – as simple as that
  • next we sort the list of these tuples – to know what comes first and what comes later.

That’s it! Let’s implement it.

2. Meeting Rooms: Optimized Implementation

2.0. Code

class Solution:
    # @param A : list of list of integers
    # @return an integer
    def solve(self, A):       
        data = [] # T: O(N), S: O(N) 
        for s, e in A:
            data.append((s, +1))
            data.append((e, -1))
        
        data.sort() # T: O(NlogN), S: O(algo)
        
        curr = 0
        ans = 0
        for _, v in data: # O(N)
            curr += v
            ans = max(ans, curr)
        return ans

2.1. Complexity Analysis

  • Time: O(NlogN), for sorting
  • Space: O(NlogN), and worst case if we use merge sort O(NlogN). There are other algorithms that different languages use that can do better.

Avatar for Tanishq Chaudhary

Producing high-quality intuitive explanations of interview problems. Currently covering LeetCode and InterviewBit.

    Comments

    1. Please write the proof.

    2. This solution need an amendment for 2 digit number.

    3. Please write a Proof for this

    4. Matt Michael D’Agati is the founder of Renewables Worldwide, an Solar Firm in MA.

      A few age ago, taking a leap of faith, Matt D’Agati delved into the realm of solar, and/or in a short occasion commenced effectively marketing significant amounts of power, primarily around the business industry, collaborating with solar farm developers and local businesses in the “design” of their unique plans.

      Ongoing marketing within the sector, offered Matthew to participate a regional startup two years in the, and in a short time, he assumed the role of their Chief Strategy Officer, in charge of all operation and endeavor improvement, in addition to being marketed social group property.

      To planned unions and shear get the job done mentality, Matthew D’Agati brought that firm from an initial initial-year revenue to in excess of a 2 hundred% surge in overall money by yr two. Based on that foundation, RW, a experienced-operated company, was produced with goal of giving you alternative electrical remedies for a more intelligent and more sustainable future.

      Even more mainly, recognizing there is an untapped market in the market place and an improved approach to realize final results, RW is one of a handful of manufactures in the u.s. to place emphasis on individual acquire, concentrating in both industrial and home solar-powered town off-take. Its visualization is to make a purchases commercial infrastructure on a community-based, statewide, countrywide level, offering various sustainable fuel goods within the of RW.

      This enthusiasm in the actual sustainable industry goes on to stimulate and inspire Matthew in enduring his solicit to work with institutions that have the unchanging of offering limitless fuel tips for a a whole lot more ecological destiny. Matt has already a new in companies from Hesser College.

      Understanding why solar energy consultants assist clients via Matthew D’Agati.
      Sustainable Energy and Electricity Poverty: Bridging the Imbalance by matt d’agatiMatt D’Agati e3d74c8

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.