N meetings in one room

Intuition

If there are two meetings, one that finishes early and another that finishes later, it is better to choose the meeting that finishes early. Choosing a meeting that ends earlier frees up the room sooner, allowing more meetings to be accommodated afterwards. By prioritizing meetings that end early, the meeting room is utilized more efficiently, maximizing the total number of meetings that can be held.

Approach

Use a vector to store pairs of start and end times of the meetings. This helps in easily accessing and sorting the meeting times.
Sort the meetings based on their end times in ascending order. This ensures that the meetings which finish earliest are considered first.
Create a variable to keep track of the end time of the last selected meeting. Also, initialize a counter to count the number of meetings that can be accommodated.
Loop through the sorted meetings and for each meeting:
- Check if the start time of the current meeting is greater than the end time of the last selected meeting.
- If true, select the current meeting, update the end time to the end time of the current meeting, and increment the counter.
After iterating through all meetings, the counter will contain the maximum number of non-overlapping meetings that can be accommodated.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Comparator function to sort meetings based on end times
    static bool comparator(const pair<int, int>& a, const pair<int, int>& b) {
        // Sort by end time in ascending order
        return a.second < b.second;
    }

    // Function to find the maximum number of meetings that can be held
    int maxMeetings(vector<int>& start, vector<int>& end) {
        int n = start.size();
        // Vector to store meetings 
        vector<pair<int, int>> meetings;
        
        // Fill the meetings vector with start and end times
        for (int i = 0; i < n; i++) {
            meetings.push_back({start[i], end[i]});
        }

        // Sort the meetings based on the custom comparator
        sort(meetings.begin(), meetings.end(), comparator);

        // The end time of last selected meeting
        int limit = meetings[0].second;
        // Initialize count
        int count = 1; 

        /*Iterate through the meetings 
        to select the maximum number 
        of non-overlapping meetings*/
        for (int i = 1; i < n; i++) {
            /*If the current meeting starts 
            after the last selected meeting ends*/
            if (meetings[i].first > limit) {
                /*Update the limit to the end 
                time of the current meeting*/
                limit = meetings[i].second;
                // Increment count
                count++;
            }
        }

        // Return count
        return count;
    }
};

int main() {
    Solution obj;
    // Start and end times of the meetings
    vector<int> start = {1, 3, 0, 5, 8, 5};
    vector<int> end = {2, 4, 6, 7, 9, 9};
    // Get the maximum number of meetings that can be held
    int maxMeetings = obj.maxMeetings(start, end);
    // Output the maximum number of meetings
    cout << "Maximum number of meetings: " << maxMeetings << endl;
    return 0;
}
import java.util.*;

class Solution {
    // Comparator function to sort meetings based on end times
    static class MeetingComparator implements Comparator<int[]> {
        public int compare(int[] a, int[] b) {
            // Sort by end time in ascending order
            return Integer.compare(a[1], b[1]);
        }
    }

    // Function to find the maximum number of meetings that can be held
    public int maxMeetings(int[] start, int[] end) {
        int n = start.length;
        // List to store meetings
        List<int[]> meetings = new ArrayList<>();
        
        // Fill the meetings list with start and end times
        for (int i = 0; i < n; i++) {
            meetings.add(new int[]{start[i], end[i]});
        }

        // Sort the meetings based on the custom comparator
        Collections.sort(meetings, new MeetingComparator());

        // The end time of last selected meeting
        int limit = meetings.get(0)[1];
        // Initialize count
        int count = 1;

        /*Iterate through the meetings 
        to select the maximum number 
        of non-overlapping meetings*/
        for (int i = 1; i < n; i++) {
            /*If the current meeting starts 
            after the last selected meeting ends*/
            if (meetings.get(i)[0] > limit) {
                /*Update the limit to the end 
                time of the current meeting*/
                limit = meetings.get(i)[1];
                // Increment count
                count++;
            }
        }

        // Return count
        return count;
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        // Start and end times of the meetings
        int[] start = {1, 3, 0, 5, 8, 5};
        int[] end = {2, 4, 6, 7, 9, 9};
        // Get the maximum number of meetings that can be held
        int maxMeetings = obj.maxMeetings(start, end);
        // Output the maximum number of meetings
        System.out.println("Maximum number of meetings: " + maxMeetings);
    }
}
class Solution:
    # Function to find the maximum number of meetings that can be held
    def maxMeetings(self, start, end):
        n = len(start)
        # List to store meetings
        meetings = []
        
        # Fill the meetings list with start and end times
        for i in range(n):
            meetings.append((start[i], end[i]))

        # Sort the meetings based on end times in ascending order
        meetings.sort(key=lambda x: x[1])

        # The end time of last selected meeting
        limit = meetings[0][1]
        # Initialize count
        count = 1

        # Iterate through the meetings to select the maximum number of non-overlapping meetings
        for i in range(1, n):
            # If the current meeting starts after the last selected meeting ends
            if meetings[i][0] > limit:
                # Update the limit to the end time of the current meeting
                limit = meetings[i][1]
                # Increment count
                count += 1

        # Return count
        return count

# Example usage
if __name__ == "__main__":
    obj = Solution()
    # Start and end times of the meetings
    start = [1, 3, 0, 5, 8, 5]
    end = [2, 4, 6, 7, 9, 9]
    # Get the maximum number of meetings that can be held
    maxMeetings = obj.maxMeetings(start, end)
    # Output the maximum number of meetings
    print("Maximum number of meetings:", maxMeetings)
class Solution {
    // Comparator function to sort meetings based on end times
    static comparator(a, b) {
        // Sort by end time in ascending order
        return a[1] - b[1];
    }

    // Function to find the maximum number of meetings that can be held
    maxMeetings(start, end) {
        const n = start.length;
        // Array to store meetings
        const meetings = [];
        
        // Fill the meetings array with start and end times
        for (let i = 0; i < n; i++) {
            meetings.push([start[i], end[i]]);
        }

        // Sort the meetings based on the custom comparator
        meetings.sort(Solution.comparator);

        // The end time of last selected meeting
        let limit = meetings[0][1];
        // Initialize count
        let count = 1;

        /*Iterate through the meetings 
        to select the maximum number 
        of non-overlapping meetings*/
        for (let i = 1; i < n; i++) {
            /*If the current meeting starts 
            after the last selected meeting ends*/
            if (meetings[i][0] > limit) {
                /*Update the limit to the end 
                time of the current meeting*/
                limit = meetings[i][1];
                // Increment count
                count++;
            }
        }

        // Return count
        return count;
    }
}

// Example usage
const obj = new Solution();
// Start and end times of the meetings
const start = [1, 3, 0, 5, 8, 5];
const end = [2, 4, 6, 7, 9, 9];
// Get the maximum number of meetings that can be held
const maxMeetings = obj.maxMeetings(start, end);
// Output the maximum number of meetings
console.log("Maximum number of meetings:", maxMeetings);

Complexity Analysis

Time Complexity: O(N+N logN) where 𝑁 is the size of the start and end arrays. The O(N) term accounts for filling the meetings array with start and end times. The O(NlogN) term arises from sorting the meetings based on their end times. After sorting, the function iterates through the sorted meetings in O(N) time to count the maximum number of non-overlapping meetings. Space Complexity: O(N) since we used an additional data structure for storing the start time and end time.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition

Approach

Dry Run

Solution

Complexity Analysis

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code