DEV Community

Wenqi Jiang
Wenqi Jiang

Posted on

Movie Theaters

#programming #cpp #algorithms #100daysofcode

Description

Given a list of time exclusive intervals for different movie showings (possibly overlapping), find the minimum number of theaters required to be able to show all movies.

Constraints:

  • • 0 ≤ n ≤ 100,000 where n is the length of intervals

Example 1

Input 

intervals = [
    [30, 75],
    [0, 50],
    [60, 150]
]
Enter fullscreen mode Exit fullscreen mode

Output 

2
Enter fullscreen mode Exit fullscreen mode

Explanation 

[30, 75] and [0, 50] overlap. [30, 75] and [60, 150] also overlap but later on. So the max number here is 2.
Enter fullscreen mode Exit fullscreen mode

Example 2

Input 

intervals = [
    [10, 20],
    [20, 30]
]
Enter fullscreen mode Exit fullscreen mode

Output 

1
Enter fullscreen mode Exit fullscreen mode

Explanation 

Boundaries are exclusive so these intervals are not considered overlapping.
Enter fullscreen mode Exit fullscreen mode

Example 3

Input 

intervals = [
    [0, 1],
    [0, 1],
    [0, 1]
]
Enter fullscreen mode Exit fullscreen mode

Output 

3
Enter fullscreen mode Exit fullscreen mode

Explanation 

The three intervals happen all at the same time so we need 3.
Enter fullscreen mode Exit fullscreen mode

Intuition

  1. sort intervals by start time increasing order
  2. create a priority_queue to store end times by increasing order
  3. compare start time and the top end time in priority queue
    1. if start time is earlier than top end time, so we need one more theater
    2. else just pop this movie out of priority queue

Implementation 

int solve(vector<vector<int>>& intervals) {
    int n = intervals.size();
    if (n <= 1) return n;
    sort(intervals.begin(), intervals.end());
    priority_queue<int, vector<int>, greater<int>> endTimes;
    endTimes.push(intervals[0][1]);
    int cnt = 1;
    for (int i = 1; i < intervals.size(); i++) {
        int startTime = intervals[i][0], endTime = intervals[i][1];
        if (startTime < endTimes.top())
            cnt++;
        else
            endTimes.pop();
        endTimes.push(endTime);
    }
    return cnt;
}
Enter fullscreen mode Exit fullscreen mode

Time Complexity

  • Time: O(nlogn)
  • Space: O(n)

Top comments (0)

Read next

shaheryaryousaf profile image

Start with Python Dictionaries

Shaheryar -

emmabase profile image

How to Implement pagination on API Endpoint Using Nodejs and TypeScript

Emmanuel Eneche -

vishalmx3 profile image

Day 8/366

vishal.codes -

rivea0 profile image

LeetCode Meditations: Linked List Cycle

Eda -