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()) {
merged.add(current);
continue;
}
Meeting lastMerged = merged.get(merged.size() - 1);
if (overlaps(lastMerged, current)) {
lastMerged.endTime = current.endTime;
} else {
merged.add(current);
}
}
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()) {
merged.add(current);
continue;
}
I think it makes the loop implementation a bit confusing, because this is only called once to add the first element to the merged elements. I wonder if using List#subList and iterating over that would be better, or a manual iterator… Also, should the Meetings become immutable, it would change the implementation a bit. Note that you are now changeing objects which are coming from the outside.
Your merge method assumes that the start time of first is always the smallest start time, and that the end time of second is always the greatest start time. This would be wrong for e.g. first = [8, 12], second = [9, 10]. It will return [8, 10], when it should be [8, 12].
The overlaps method also is a bit incorrect, because multiple meetings starting at the same point in time will not be merged. Also (first.endTime == second.startTime || second.startTime < first.endTime) is the same as second.startTime <= first.endTime.
Finally, your show method ends each line with a comma. Should you want to simply delimit each meeting with a comma, but not one at the end of the line, you could solve it for example as:
System.out.println(meetings.stream().map(Meeting::toString).collect(joining(",")));