logo标签列表

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

data-structures
4
我被要求设计一种数据结构来管理会议日程，并将它们合并。例如，如果A有从上午9:00到10:00的会议，而B有从上午9:30到11:30的会议，则合并后的忙碌时间段是从上午9:00到11:30。
我为Person类创建了集合，这个类包含了Meeting对象的集合。Meeting类具有24小时制的开始时间[hh：mm]，以便我可以进行比较。
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。

欢迎提出更好的设计。

所有人的会议应合并以找出总体繁忙时间段吗？ - Roman Byshko
是的。结果应该包括繁忙时间和空闲时间，这样每个人都可以查看并知道什么时间适合所有人。 - wayfare
4个回答
2

由于安排小于15分钟的时间段进行会议是不现实的，我可以使用一个long。每天64位足以支持16小时；我并不需要那么多。或者如果您愿意，可以使用两个longs /三个ints来表示一整天。

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

2

如@Anonymouse所建议的，您可以使用96位即12个字节来表示一天，因此从1:00 AM开始的30分钟会议将表示为110000，您可以在所有数字上使用简单的|操作。

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

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

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

Sc [minimum(SA-start,SB-start),maximum(SA-end,SB-end)]，并将合并后的会议存储在集合中。如果不重叠，则可以将它们分开存储。

我们知道一天的总分钟数= 24 * 60 = 1440 如果您有15分钟的单位，则变为24 * 60 / 15 = 96（小于1字节）

因此，每个日程需要2个字节，即字节开始，结束。

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

如果您以后必须删除会议，则这两种方法都无法使用。对于这个问题，您肯定需要单独保留所有原始会议安排。

0

计算不合并日程表的空闲时间：

  • 员工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() {

    // 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]");
      }
    }       
 }
-1
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接