# Let us schedule a meeting

Posted on

Problem

Description:

Write a method mergeMeetings() that takes a list of multiple meeting time ranges and returns a list of condensed ranges. The integers represent the number of 30-minute blocks past 9:00am.

Do not assume the meetings are in order. The meeting times are coming from multiple teams.

Code:

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.ArrayList;

class Meeting {
int startTime;
int endTime;

Meeting(int startTime, int endTime) {
this.startTime = startTime;
this.endTime = endTime;
}

public String toString() {
return startTime + " : " + endTime;
}
}

class Main {
static List<Meeting> mergeMeetings(List<Meeting> meetings) {
for (int outer = 0; outer < meetings.size(); outer++) {
Meeting outerMeeting = meetings.get(outer);

for (int inner = 0; inner < meetings.size(); inner++) {
Meeting innerMeeting = meetings.get(inner);

if (overlaps(outerMeeting, innerMeeting)) {
meetings.set(outer, merge(outerMeeting, innerMeeting));
meetings.remove(inner);
break;
}
}
}
return meetings;
}

static List<Meeting> mergeMeetings2(List<Meeting> meetings) {
List<Meeting> merged = new ArrayList<>();

Collections.sort(meetings, (a, b) -> a.startTime - b.startTime);

for (Meeting current : meetings) {
if (merged.isEmpty()) {
continue;
}
Meeting lastMerged = merged.get(merged.size() - 1);
if (overlaps(lastMerged, current)) {
lastMerged.endTime = current.endTime;
} else {
}
}
return merged;
}

private static Meeting merge(Meeting first, Meeting second) {
return new Meeting(first.startTime, second.endTime);
}

private static boolean overlaps(Meeting first, Meeting second) {
return first.startTime < second.startTime &&
(first.endTime == second.startTime || second.startTime < first.endTime);
}

static void show(List<Meeting> meetings) {
for (Meeting meeting : meetings) {
System.out.print(meeting + ", ");
}
System.out.println();
}

public static void main(String[] args) {
show(mergeMeetings(new ArrayList(Arrays.asList(
new Meeting(0, 1),
new Meeting(3, 5),
new Meeting(4, 8),
new Meeting(10, 12),
new Meeting(9, 10)
)))); // 0 1, 3 8, 9 12

show(mergeMeetings2(new ArrayList(Arrays.asList(
new Meeting(0, 1),
new Meeting(3, 5),
new Meeting(4, 8),
new Meeting(10, 12),
new Meeting(9, 10)
)))); // 0 1, 3 8, 9 12

show(mergeMeetings(new ArrayList(Arrays.asList(
new Meeting(1, 4),
new Meeting(4, 5)
)))); // 1 5

show(mergeMeetings2(new ArrayList(Arrays.asList(
new Meeting(1, 4),
new Meeting(4, 5)
)))); // 1 5

show(mergeMeetings(new ArrayList(Arrays.asList(
new Meeting(1, 3),
new Meeting(2, 6),
new Meeting(8, 10),
new Meeting(15, 18)
)))); // 1 6, 8 10, 15 18

show(mergeMeetings2(new ArrayList(Arrays.asList(
new Meeting(1, 3),
new Meeting(2, 6),
new Meeting(8, 10),
new Meeting(15, 18)
)))); // 1 6, 8 10, 15 18
}
}

Note:

The brute force solution is intentional and I am practicing it to at least
come up with the brute force answer if not able to find the optimal solution. I am learning to quickly find little abstractions to help me think about the solution more easily for eg: the two helper methods overlaps and merge helped me to find the solution easily.

Questions:

Apart from general code review I would like to know more tips / recommendations on coming up with brute force solutions quickly.

Solution

Not sure if I should review it as a programming challenge, or if I should include design remarks, I’ll just say what comes to mind.

I’ll first note that I would make the Meeting fields private final, and add accessor methods. Them being immutable makes sense I would say, and methods help for using them as method references with the streaming API and others, as I will show in a second.

For mergeMeetings, I would really refrain from using set and remove, at least when you do not know the implementation. Depending on the List implementation, the performance of these could turn out to be quite horrible (e.g. set could traverse the list up to the index each time in case of a LinkedList). Also looping and mutating a collection at the same time is a lot of times error-prone or worse. Finally, you mutate the collection passed in, which is also a point to think about twice (though not necessarily bad).

For mergeMeetings2, I like this implementation better. It is a smarter implementation for given problem. First, I would like to note that since Java 8, Collection has a default method implementation for sort. Next, with the Comparator#comparing method, you can specify which property of the type to use to compare with. If you add accessor methods like stated before, this would make the sort look like (with a static import of Comparator):

meetings.sort(comparingInt(Meeting::startTime));

Perhaps instead of using a List to keep track of the merged meetings, you could use a stack (though do not use Stack, rather something like ArrayDeque, refer to the docs why). Instead of getting the last element from the list, you just peek the top, and pop if you have to merge again. I am not sure how I feel about

if (merged.isEmpty()) {