Intervals with Exactly X Concurrent Meetings

Question

The question asks the candidate to determine the number of intervals that have exactly X concurrent meetings occurring at the same time.

Codemia · Accepted Answer

To solve the problem of finding intervals with exactly X concurrent meetings, we first need to clarify the input format. We will receive a list of meeting intervals, where each interval is defined by a start and end time. Our goal is to count how many intervals have exactly X meetings happening at any given time.

We can use a sweep line algorithm to efficiently count concurrent meetings. The idea is to create two events for each meeting: a start event and an end event. We will then sort these events and process them in order, maintaining a count of active meetings at any point in time.

1. Create a list of events from the meeting intervals.
2. Sort the events: first by time, then by type (end before start if they are at the same time).
3. Initialize a counter for active meetings and a result counter for intervals with exactly X meetings.
4. Iterate through the sorted events, updating the active meetings count and checking if it equals X.
5. If it does, increment the result counter.

Here is a Python implementation:
```python
def count_intervals_with_exactly_x_concurrent_meetings(intervals, x):
    events = []
    for start, end in intervals:
        events.append((start, 'start'))
        events.append((end, 'end'))

events.sort(key=lambda event: (event[0], event[1] == 'end'))

active_meetings = 0
    count_exact_x = 0

for time, event_type in events:
        if event_type == 'start':
            active_meetings += 1
        else:
            if active_meetings == x:
                count_exact_x += 1
            active_meetings -= 1

return count_exact_x
```

The time complexity of this approach is O(N log N) due to the sorting step, where N is the number of meetings. The space complexity is O(N) for storing the events. This is efficient enough for a large number of meetings.

We should consider edge cases such as:
- No meetings at all, which should return 0.
- Meetings that start and end at the same time, ensuring they are counted correctly.
- All meetings overlapping, which should be handled by the algorithm without issues.

Intervals with Exactly X Concurrent Meetings

Google

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Framing

Approach

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string