Java - N Meetings in One Room

Problem Statement

You are given N meetings with their start and end times. You have one meeting room, and only one meeting can take place at a time. Find the maximum number of meetings that can be scheduled without overlapping.

Example 1:

Input:

N = 6

start = {1, 3, 0, 5, 8, 5}

end = {2, 4, 6, 7, 9, 9}

Output: 4

Explanation:

The maximum number of meetings that can be scheduled is **4**. The meetings selected are:

1. (1,2)

2. (3,4)

3. (5,7)

4. (8,9)

Example 2:

Input:

N = 3

start = {10, 12, 20}

end = {20, 25, 30}

Output: 3

Explanation:

All 3 meetings can be scheduled as they do not overlap.

Approach: Greedy Algorithm

Key Idea:

Sort the meetings by their end time (earliest finishing first).

Pick the meeting that finishes the earliest and then move to the next non-overlapping meeting.

Algorithm:

Pair each meeting's start and end times together.

Sort meetings by end time.

Iterate through the sorted meetings:

If a meeting starts after the last selected meeting ends, select it.

Update the end time reference.

Return the count of selected meetings.

Implementation:

import java.util.*;

class Meeting {

int start, end;

Meeting(int start, int end) {

this.start = start;

this.end = end;

}

public class NMeetingsInOneRoom {

public static int maxMeetings(int[] start, int[] end, int N) {

List<Meeting> meetings = new ArrayList<>();

// Step 1: Create Meeting objects

for (int i = 0; i < N; i++) {

meetings.add(new Meeting(start[i], end[i]));

}

// Step 2: Sort meetings by end time

meetings.sort(Comparator.comparingInt(m -> m.end));

// Step 3: Select meetings

int count = 0;

int lastEndTime = -1;

for (Meeting meeting : meetings) {

if (meeting.start > lastEndTime) {

count++;

lastEndTime = meeting.end; // Update the last meeting's end time

}

return count;

}

public static void main(String[] args) {

int N = 6;

int[] start = {1, 3, 0, 5, 8, 5};

int[] end = {2, 4, 6, 7, 9, 9};

System.out.println("Maximum number of meetings: " + maxMeetings(start, end, N));

// Output: 4

}

Complexity Analysis

Step Time Complexity

Sorting meetings O(N log N)

Iterating through meetings O(N)

Total Complexity O(N log N)

Space Complexity:

O(N) (for storing meeting objects).

If input can be modified, sorting start[] and end[] directly reduces space to O(1).

Edge Cases Considered

✔ Meetings already sorted by end time → Works correctly.

✔ All meetings overlap → Returns 1.

✔ All meetings fit → Returns N.

✔ Meetings with same end times → Handled correctly by sorting.

Optimized Version (Using Arrays Instead of Objects)

If memory usage is a concern, we can avoid creating objects and use arrays directly:

import java.util.Arrays;

public class NMeetingsOptimized {

public static int maxMeetings(int[] start, int[] end, int N) {

int[][] meetings = new int[N][2];

// Pair start and end times

for (int i = 0; i < N; i++) {

meetings[i][0] = start[i]; // Start time

meetings[i][1] = end[i]; // End time

}

// Step 2: Sort by end time

Arrays.sort(meetings, Comparator.comparingInt(m -> m[1]));

// Step 3: Select meetings greedily

int count = 0, lastEndTime = -1;

for (int[] meeting : meetings) {

if (meeting[0] > lastEndTime) {