计算不合并日程表的空闲时间:
- 员工1的可用时间(bounds):[9:00至20:00]
- 员工1的繁忙时间段:[[9:00, 10:30],[12:00, 13:00],[16:00, 18:00]]
- 员工2的可用时间(bounds):[10:00至18:30]
- 员工2的繁忙时间段:[[10:00, 11:30],[12:30,14:30],[14:30, 15:00],[16:00, 17:00]]
- 空闲时间段:[[11:30, 12:00],[15:00, 16:00],[18:00, 18:30]]
- 程序输出结果:[11h:30m - 12h:00m] [15h:00m - 16h:00m] [18h:00m - 18h:30m]
这是我的方法:我不合并日历来计算空闲时间,而是使用TreeMap将忙碌的日程标记为“B”,将空闲时间标记为“F”。我考虑了下限和上限内的每一分钟。最初,假设从下限到上限都有空闲时间,地图将被更新为“F”。稍后,地图将被更新为忙碌的日程。时间复杂度为O(n*2),因为间隔是一个列表,每个间隔都需要处理以更新地图。空间复杂度为O(n)。
ScheduleFinderTest test = new ScheduleFinderTest();
test.findFreeSchedules();
public class ScheduleFinderTest {
public void findFreeSchedules() {
MeetingIntervals bound = new MeetingIntervals(9, 00, 20, 00);
MeetingIntervals busyInterval1 = new MeetingIntervals(9, 00, 10, 30);
MeetingIntervals busyInterval2 = new MeetingIntervals(12, 00, 13, 00);
MeetingIntervals busyInterval3 = new MeetingIntervals(16, 00, 18, 00);
List<MeetingIntervals> allBusyIntervals1 = Arrays.asList(busyInterval1, busyInterval2, busyInterval3);
Employee e1 = new Employee("John", bound, allBusyIntervals1);
bound = new MeetingIntervals(10, 00, 18, 30);
busyInterval1 = new MeetingIntervals(10, 00, 11, 30);
busyInterval2 = new MeetingIntervals(12, 30, 14, 30);
busyInterval3 = new MeetingIntervals(14, 30, 15, 00);
MeetingIntervals busyInterval4 = new MeetingIntervals(16, 00, 17, 00);
List<MeetingIntervals> allBusyIntervals2 = Arrays.asList(busyInterval1, busyInterval2, busyInterval3, busyInterval4);
Employee e2 = new Employee("Christiana", bound, allBusyIntervals2);
ScheduleFinder scheduleFinder = new ScheduleFinder(Arrays.asList(e1, e2));
scheduleFinder.find();
}
}
@Data
@AllArgsConstructor
class Employee {
private String name;
private MeetingIntervals bounds;
private List<MeetingIntervals> intervals;
}
@Data
@AllArgsConstructor
class MeetingIntervals {
private int fromHour;
private int fromMinutes;
private int toHour;
private int toMinutes;
}
public class ScheduleFinder {
private List<Employee> employees;
public ScheduleFinder(List<Employee> employees) {
this.employees = employees;
}
public void find() {
Collections.sort(employees, (e1, e2) -> e2.getBounds().getFromHour() - e1.getBounds().getFromHour());
int inTimeHour = employees.get(0).getBounds().getFromHour();
int inTimeMinutes = employees.get(0).getBounds().getFromMinutes();
Collections.sort(employees, (e1, e2)-> e1.getBounds().getToHour() - e2.getBounds().getToHour());
int exitTimeHour = employees.get(0).getBounds().getToHour();
int exitTimeMinutes = employees.get(0).getBounds().getToMinutes();
MeetingIntervals availableInterval = new MeetingIntervals(inTimeHour, inTimeMinutes, exitTimeHour, exitTimeMinutes);
Map<String, Character> scheduleMap = new TreeMap<>();
updateSchedule(availableInterval, scheduleMap, 'F');
System.out.println(scheduleMap);
List<MeetingIntervals> allBusyIntervals = employees.stream()
.flatMap(m -> m.getIntervals().stream())
.collect(Collectors.toList());
Collections.sort(allBusyIntervals, (e1, e2) -> e1.getFromHour() - e2.getFromHour());
updateScheduleMap(allBusyIntervals, scheduleMap, 'B');
System.out.println(scheduleMap);
printFreeSchedules(scheduleMap, exitTimeHour, exitTimeMinutes);
}
private void updateScheduleMap(List<MeetingIntervals> busyIntervals, Map<String, Character> scheduleMap, char marker) {
for (MeetingIntervals interval : busyIntervals) {
updateSchedule(interval, scheduleMap, marker);
}
}
private void updateSchedule(MeetingIntervals interval, Map<String, Character> map, char marker) {
int startTimeHour = interval.getFromHour();
int startTimeMinutes = interval.getFromMinutes();
int startTimeInMinutes = getTimeInMinutes( startTimeHour, startTimeMinutes);
int endTimeInMinutes = getTimeInMinutes( interval.getToHour(), interval.getToMinutes());
for (int i = 0; i < (endTimeInMinutes - startTimeInMinutes); i++) {
String key = getFormattedKey(startTimeHour, startTimeMinutes);
if (marker == 'B' && map.get(key) != null) {
map.put(key, marker);
} else if (marker == 'F' && map.get(key) == null) {
map.put(key, marker);
}
++startTimeMinutes;
if (startTimeMinutes == 60) {
startTimeMinutes = 0;
++startTimeHour;
}
}
}
private int getTimeInMinutes(int hour, int minutes) {
return ( hour * 60 ) + minutes ;
}
public String getFormattedKey(int hour, int minutes) {
StringBuilder sb = new StringBuilder();
String hourStr = hour + "";
String minutesStr = minutes + "";
if (String.valueOf(hour).length() == 1) {
hourStr = "0" + hour;
}
if (String.valueOf(minutes).length() == 1) {
minutesStr = "0" + minutes;
}
sb.append(hourStr).append("h:").append(minutesStr).append("m");
return sb.toString();
}
private void printFreeSchedules(Map<String, Character> scheduleMap, int exitTimeHour, int exitTimeMinutes) {
boolean intervalStarted = false;
boolean intervalEnded = false;
for(String k : scheduleMap.keySet()) {
if ( scheduleMap.get(k) == 'F' && intervalStarted == false) {
System.out.print("[" + k);
intervalStarted = true;
intervalEnded = false;
}
if ( scheduleMap.get(k) == 'B' && intervalStarted == true && intervalEnded == false) {
System.out.println(" - " + k + "]");
intervalEnded = true;
intervalStarted = false;
}
}
if ( intervalStarted == true && intervalEnded == false ) {
System.out.println(" - " + exitTimeHour + "h:" + exitTimeMinutes + "m]");
}
}
}