设计合并会议日程的数据结构

Question

我被要求为会议日程设计一个数据结构，然后将它们合并。例如，如果人员 A 的会议时间为上午 9:00 到上午 10:00，人员 B 的会议时间为上午 9:30 到上午 11:30，则合并的繁忙时段为上午 9:00 到上午 11:30。

我为 Person 创建了类，该类包含会议对象的集合。 Meeting 类的开始时间 [hh:mm] 采用 24 小时格式，以便我可以轻松进行比较。

class Person {
String name;
Collection<Meeting> meetings;

}


class Meeting{
int hh, mm;
int duration; // duration will be in minutes from where we can get the end time. 
}

我想知道哪种数据结构对于合并最有效。 一种方法是使用会议排序的ArrayList。

任何更好的设计都值得赞赏。

Answer 1

由于安排会议时间少于 15 分钟是不现实的，所以我会选择......长。每天64位，足够16个小时；我不需要那么多。或者，如果您愿意，可以在一整天内使用两个长整型/三个整型。

合并是一个 | 操作。对于较大的时间段，我可以移动或移动它们，然后检查未设置的位作为会议开始时间。这种高度压缩的数据结构将击败任何索引，仅仅因为低级操作。 CPU缓存可以满足数百天/用户的调度。

Answer 2

在不合并计划的情况下计算空闲时段：

• 员工 1 可用性（范围）：[9:00 至 20:00]
• 员工 1 繁忙计划间隔：
  [[9:00, 10:30],[12:00, 13:00],[16:00, 18:00]]
• 员工 2 空闲（范围）：[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() {

    // Employee availability time ( 9:00 to 12:00 )
    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);

    // Employee availability time ( 10:00 to 18:30 )
    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() {

    // sort all bound hours (from availability)  and get the maximum one
    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();

    // sort all bound hours ( to availability ) and get the minimum one
    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();

    // initially mark the map with free time for bounds as calculated above
    MeetingIntervals availableInterval = new MeetingIntervals(inTimeHour, inTimeMinutes, exitTimeHour, exitTimeMinutes);        
    Map<String, Character> scheduleMap = new TreeMap<>();
    updateSchedule(availableInterval, scheduleMap, 'F');
    System.out.println(scheduleMap);

    // update the map with busy intervals
    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);

    // print free schedules
    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]");
      }
    }       
 }

Answer 3

这是任务调度的经典问题。

Answer 4

正如 @Anonymouse 建议的那样，您可以使用 96 位（即 12 个字节）来表示一天，因此从凌晨 1:00 开始的 30 分钟会议将表示为 110000，您可以使用简单的 | 。对所有数字进行操作。

时间 O(n) 内存 O(12n) 字节。理论上会快得多。

---

给定一个会议[开始时间（以分钟为单位），结束时间（以分钟为单位）]。

当 Sc重叠时，将两个会议（Sa 和 Sb）合并到 Sc 中

[最小值（SA-start，SB-start），最大值（SA-end，SB-end）] 并将合并的会议存储在集合中。如果不重叠，则可以单独存储它们。

我们知道一天的总分钟数 = 24 * 60 = 1440
如果您有 15 分钟单位，那么它会变成 24 * 60 / 15 = 96（低于 1 字节），

因此每个计划需要 2 字节，即字节开始、结束。

时间 O(n) 内存 O(2n) 字节

---

如果您稍后必须删除会议，这两种方法都不起作用。为此，您肯定会单独举行所有原始会议日程。