Maximum meetings

Pratice here

You are given the schedule of N meetings with their start time Start[i] and end time End[i].

You have only 1 meeting room. So, you need to return the maximum number of meetings you can organize.

Intiution#

Goal?

• Schedule the maximum number of non-overlapping meetings.
• Two meetings overlap if one starts before the other ends.

Idea?

• Always choose the meeting that ends earliest. Reason: It frees the room sooner → allows more meetings later.
• If two meetings end at the same time, pick the one that starts earlier (tie-breaker).

Greedy Approach#

The greedy insight from the Intuition section above directly drives the algorithm: sorting by end time and always greedily picking the next meeting that doesn’t conflict is provably optimal — choosing any later-ending meeting can only reduce the room availability for future meetings.

• Combine start and end into intervals.
• Sort by end time (primary), and start time (secondary).
• Iterate:
  • If the current meeting starts after the last chosen meeting ends, select it.
  • Update lastIdx to current meeting’s end.

Trade-off: Sorting costs O(N log N) and dominates the O(N) linear scan. The extra O(N) space holds the paired intervals. This is optimal — any algorithm must examine all meetings, and sorting is necessary to make greedy choices efficiently.

int maximumMeetings(vector<int> &start, vector<int> &end)
{
    vector<vector<int>> intervals;
    for(int i=0;i<start.size();i++){
        intervals.push_back({start[i], end[i]});
    }

    sort(intervals.begin(), intervals.end(), 
        [](const vector<int> &a, const vector<int> &b){
            if(a[1]==b[1])
                return a[0] < b[0];
            return a[1]<b[1];
    });

    int lastIdx = -1, countNonOverlappingIntervals=0;
    for(int i=0;i<intervals.size();i++)
    {
        if(intervals[i][0] > lastIdx)
        {
            countNonOverlappingIntervals++;
            lastIdx = intervals[i][1];
        }
    }
    return countNonOverlappingIntervals;
}

Time Complexity: O(N * logN)

Space Complexity: O(N)