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.