Algorithme pour trouver le maximum de classes suivies par l'élève | problème de sélection d'activité

Je l'ai essayé avec Python. Il donne une sortie correcte. Je l'ai trié par heure de début du cours.

A student can attend these combinations of subject classes:  {('Physics', 'Maths'), ('Physics', 'Chemistry'), ('ComputerScience', 'Chemistry'), ('Compu
terScience', 'Maths')}
Maximum classes student can attend in a day is:  2

Ici, la partie astuce consiste à décider du nombre de combinaisons que vous pouvez faire. Donc, vous pouvez le faire en ajoutant une boucle for supplémentaire allant de 2 à la longueur de sorted_list et en passant i à des combinaisons (sorted_list, i) comme ceci.

La fin est:

sorted_by_start = [{'sub': 'ComputerScience', 'start': '12:00', 'end': '13:00', 
'duration': 60}, {'sub': 'Physics', 'start': '12:30', 'end': '14:00', 'duration': 
90}, {'sub': 'Chemistry', 'start': '14:00', 'end': '16:30', 'duration': 150}, 
{'sub': 'Maths', 'start': '16:00', 'end': '18:00', 'duration': 120}]

possible_sub = set()

for a, b in itertools.combinations(sorted_by_start, 2):
    strt_tme = datetime.datetime.strptime(a["end"], '%H:%M')
    end_tme = datetime.datetime.strptime(b["start"], '%H:%M')
      if(strt_tme <= end_tme) :
        possible_sub.add((a["sub"],b["sub"]))

print("A student can attend these combinations of subject classes:",possible_sub)
print("Maximum classes student can attend in a day is: ",max(map(len,possible_sub)))

Ceci est connu dans la littérature sous le nom de Problème de planification d'intervalle . Il existe de nombreuses façons de le résoudre, mais comme il s'agit de NP-complete (car il y a une réduction polynomiale de VC) vous devrez nécessairement explorer toutes les combinaisons.

Des algorithmes gourmands existent ( comme c'est le vôtre et la solution de @PriyankaDeshmukh), mais ils ne vous garantissent pas la solution exacte pour toutes les instances du problème.

La solution ci-dessous est une simple recherche arborescente: à chaque niveau, nous décidons si nous suivons un cours donné ou pas et passons à la décision du cours suivant.

Vous pouvez également implémenter une solution de programmation dynamique.

Voici un très bon article de blog couvrant les solutions au Planification d'intervalle Problème.

J'ai modélisé une classe d'élèves de la manière suivante:

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());
}

Il existe des classes pour représenter l'heure de la journée, mais leur syntaxe / instanciation est un peu ennuyeux / verbeux - n'hésitez pas à améliorer cette réponse! Mon Java est également très rouillé, alors n'hésitez pas à me corriger :-)

La classe Schedule a un getMaxSchedule () qui renvoie la solution au problème - quel est le nombre maximum de cours qu'un élève peut suivre, de sorte qu'aucun d'entre eux ne se chevauche?

Il y a plusieurs façons de l'optimiser, mais je l'ai laissé tel quel car je pense que c'est plus facile à comprendre .

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);
    }
}

Vous pouvez voir que le résultat est 3 pour votre problème concret à travers ce qui suit:

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;
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class InputSubject implements Comparable<InputSubject>{
    String subject;
    String startTime;
    String endTime;
    InputSubject(){
        
    }
    InputSubject(String subject, String startTime, String endTime){
        this.subject = subject;
        this.startTime = startTime;
        this.endTime =  endTime;
    }
    
    public String getSubject() {
        return subject;
    }
    public void setSubject(String subject) {
        this.subject = subject;
    }
    public String getStartTime() {
        return startTime;
    }
    public void setStartTime(String startTime) {
        this.startTime = startTime;
    }
    public String getEndTime() {
        return endTime;
    }
    public void setEndTime(String endTime) {
        this.endTime = endTime;
    }
    @Override
    public int compareTo(InputSubject o) {
        
        return this.endTime.compareTo(o.endTime);
    }

}

public class SubjectSort {
    
    static int getToatlSubject(List<InputSubject> list){
        String sTime = null;
        String eTime =  null;
        int count = 0;
        int noOfSubject = 0;
        for(InputSubject object : list){
            if(count == 0){
                count++;
                eTime = object.getEndTime();
                noOfSubject ++;
            }
            else {
                if(object.getStartTime().compareTo(eTime) > 0){
                    eTime = object.getEndTime();
                    noOfSubject ++;
                }
            }
        }
        return noOfSubject;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        try {
            int days = Integer.parseInt(reader.readLine());
            for(int i = 0 ; i < days ;i++){
                int sub = Integer.parseInt(reader.readLine());
                List<InputSubject> list = new ArrayList<>();
                for(int k = 0 ; k < sub ; k++){
                    InputSubject inputSubject = null;
                    String subDetails =  reader.readLine();
                    String[] subAndTimes = subDetails.split(" ");
                    inputSubject = new InputSubject(subAndTimes[0],subAndTimes[1],subAndTimes[2]);
                    list.add(inputSubject);
                }
                Collections.sort(list);
                System.out.println(getToatlSubject(list));
            }
        
        } catch (Exception e) {
        }

    }

}

J'ai eu la même question lors d'un cycle de codage d'un recrutement et je l'ai résolue de la manière suivante et elle donne la bonne réponse. Mais malheureusement, ce code n'a réussi qu'un seul cas de test donné dans le défi. Je pense que les cas de test étaient incorrects. Quelqu'un peut-il signaler si j'ai manqué quelque chose dans le code qui aurait pu amener ce code à échouer dans d'autres cas de test?

import java.util.*;
import java.time.*;
import java.time.format.DateTimeFormatter; 
import static java.time.temporal.ChronoUnit.*;

class solution {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for (int i = 0; i < t; i++) {
            int n=sc.nextInt();
            String trash=sc.nextLine();
            HashMap subjects=new HashMap<String,String>();
            HashMap starttime=new HashMap<String,LocalTime>();
            HashMap endtime=new HashMap<String,LocalTime>();
            HashMap length=new HashMap<String,Long>();
            for (int j = 0; j < n; j++){
                String classes = sc.nextLine();
                String[] classesArray=classes.split(" ");
                String subject=classesArray[0];
                if(classesArray[1].split(":")[0].length()==1){
                    classesArray[1]="0"+classesArray[1];
                }
                if(classesArray[2].split(":")[0].length()==1){
                    classesArray[2]="0"+classesArray[2];
                }
                LocalTime startTime=LocalTime.parse(classesArray[1]);
                LocalTime endTime=LocalTime.parse(classesArray[2]);
                DateTimeFormatter formatter = DateTimeFormatter.ISO_TIME; 
                Long lengthLecture=MINUTES.between(startTime, endTime);
                subjects.put(subject,subject);
                starttime.put(subject,startTime);
                endtime.put(subject,endTime);
                length.put(subject,lengthLecture);
                // String value = startTime.format(formatter);
                // String value1 = endTime.format(formatter);
                // System.out.printf("Sub:%s st:%s et:%s length:%d\n",subject,value,value1,lengthLecture);
            }
            findMax(subjects,starttime,endtime,length);
            //System.out.println(num);
        }
    }
    public static void findMax(HashMap<String,String> subs,HashMap<String,LocalTime> strt,HashMap<String,LocalTime> endt,HashMap<String,Long> length){
       int number=0;
       List<Integer> list = new ArrayList<Integer>();
       String curr,next1;
      for (Map.Entry<String,String> entry : subs.entrySet()){
       //System.out.println("Checkign for number: "+entry.getKey());
       number=findnext(entry.getKey(),strt,endt);
      // System.out.println("Number is: "+number);
       list.add(number);
      }
      System.out.println(Collections.max(list));
    }
   
    public static int findnext(String subjt,HashMap<String,LocalTime> strt,HashMap<String,LocalTime> endt){
        String sub=subjt;
        int number=1;
        LocalTime substtime=strt.get(earliest);
        LocalTime subedtime=endt.get(earliest);
        Long timetillstart=922337203L;
        for (Map.Entry<String,LocalTime> entry : strt.entrySet()){
            if((entry.getValue().compareTo(subedtime)>=0) && (MINUTES.between(subedtime, entry.getValue())<=timetillstart)){
                sub=entry.getKey();
                substtime=strt.get(entry.getKey());
                timetillstart=MINUTES.between(subedtime, entry.getValue());
            }
        }
        if(sub!=subjt){
            number=number+findnext(sub,strt,endt);
        }
        return number;
    }
}