Это известно в литературе как Проблема планирования интервалов .Есть много способов ее решить, но так как она 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(), который возвращает решение проблемы - какое максимальное количество классов aстудент может взять, чтобы ни один из них не перекрывался?
Есть несколько способов оптимизировать его, но я оставил его как есть, так как считаю, что его легче понять.
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> 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);
}
}
Вы можете увидеть результат 3 для вашей конкретной проблемы с помощью следующего:
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());
}