求解学生活动选择问题的最大班级数算法

Question

输入格式

• 第一行包含一个整数n，它给出了当天提供的主题数量。
• 接下来的n行包含主题名称（是一个字符串），然后是该主题的24小时格式的开始和结束时间:hh:mm

例如:Maths 10:00 11:00
注意：时间是以24小时的格式给出的，主题名称之间没有空格。

4
Maths 16:00 18:00
ComputerScience 12:00 13:00
Physics 12:30 14:00
Chemistry 14:00 16:30

2

解释
计算机科学开始最早，结束最早，所以我们先取。在那之后，我们不能选物理，因为它在计算机科学结束之前就开始了。所以我们要上下一节课，也就是化学。但是化学之后我们不能上数学课，因为数学课在化学课结束之前就开始了。所以我们一天最多可以安排两节课。

以下是我的解决方案，但我没有得到正确的答案：

private void getMaxClass(String input) {

    Map<String, Long> classTime = new LinkedHashMap<>();
    Map<String, List<String>> timeMap = new LinkedHashMap<>();
    String[] split = input.split(" ");
    String subject = split[0];
    String StartTime = split[1];
    String endTime = split[2];
    List<String> lvalue = new ArrayList<>();
    lvalue.add(StartTime);
    lvalue.add(endTime);
    timeMap.put(subject, lvalue);
    long difference = FineDifferenceInTime(StartTime, endTime);
    classTime.put(subject, difference);
    int count = 0;
    Date date1 = null;
    Date date2 = null;
    Map<String, Long> sortedByValueDesc = classTime.entrySet().stream()
            .sorted(Map.Entry.<String, Long>comparingByValue())
            .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue, (e1, e2) -> e1, LinkedHashMap::new));
    for (Map.Entry<String, Long> entry : sortedByValueDesc.entrySet()) {
        String sub = entry.getKey();
        List<String> startEnd = timeMap.get(sub);
        Date dateBefore = null;
        Date dateAfter = null;
        SimpleDateFormat format = new SimpleDateFormat("HH:mm");
        try {
            dateBefore = format.parse(startEnd.get(0));
            dateAfter = format.parse(startEnd.get(1));
        } catch (ParseException e) {
            e.printStackTrace();
        }
        if (count == 0) {
            count++;
            try {
                date1 = format.parse(startEnd.get(0));
                date2 = format.parse(startEnd.get(1));
            } catch (ParseException e) {
                e.printStackTrace();
            }
        }
        if (dateBefore.after(date1) && dateBefore.before(date2)) {
            timeMap.remove(sub);
        }
    }
    System.out.println(timeMap.size());
}

Answer 1

这在文献中被称为区间调度问题。有很多方法来解决它，但由于它是NP完全的（因为有一个多项式约简从VC），你必须探索所有的组合。

贪婪算法确实存在（你的算法和@Priyankadeshmukh的解决方案也是如此），但它们不能保证所有问题的精确解。

下面的解决方案是一个简单的树搜索：在每个级别上，我们决定是否选择一门给定的课程，然后继续决定下一门课程。

class StudentClass {
    public int _start;
    public int _end;
    public String _name;
    public StudentClass(String name, int start, int end) {
        _name = name;
        _start = start;
        _end = end;
    }
    public boolean overlapsWith(StudentClass other) {
        return _start < other._end && _end > other._start;
    }
    public String toString() {
        return "[" + _start + " - " + _end + "] " + _name;
    }
}

有一些类来表示一天中的时间，但是它们的语法/实例化有点烦人/冗长--尽管可以改进这个答案！我的Java也很生疏，请随时纠正我：-）

Schedule类有一个getmaxschedule()，它返回问题的解决方案--学生可以上的最大类数是多少，这样它们就不会重叠了？

有几种方法来优化它，但我让它保持原样，因为我相信它更容易被理解。

public class Schedule {

    List<StudentClass> _classes = new LinkedList<>();

    public void addClass(String name, int startTime, int endTime) {
        _classes.add(new StudentClass(name, startTime, endTime));
    }

    private int getMaxSchedule(int index, Collection<StudentClass> html" target="_blank">selected) {
        // check if we reached the end of the array
        if (index >= _classes.size()) {
            return 0;
        }

        StudentClass current = _classes.get(index);

        // check if taking this class doesn't conflict with the
        // previously-selected set of classes
        boolean canTakeThisClass = true;
        for (StudentClass other : selected) {
            if (current.overlapsWith(other)) {
                canTakeThisClass = false;
                break;
            }
        }

        // check best schedule if we don't take this class
        int best = getMaxSchedule(index + 1, selected);

        // check best schedule if we take this class (if such is possible)
        if (canTakeThisClass) {
            selected.add(current);
            best = Math.max(best, 1 + getMaxSchedule(index + 1, selected));
            selected.remove(current);
        }

        return best;
    }

    public int getMaxSchedule() {
        Collection<StudentClass> selected = new ArrayList<>();
        return getMaxSchedule(0, selected);
    }
}

public static void main(String[] args) {
    Schedule s = new Schedule();
    s.addClass("Maths", 1600, 1800);
    s.addClass("Computer Science", 1200, 1300);
    s.addClass("Physics", 1230, 1400);
    s.addClass("Chemistry", 1400, 1630);
    System.out.println("maximum classes: " + s.getMaxSchedule());
}