fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. // Function to check if assigning a time slot to a class is safe
  7. bool isSafe(int classIndex, vector<vector<int>>& conflicts, vector<int>& timeSlot, int slot) {
  8.     for (int i = 0; i < conflicts.size(); i++) {
  9.         if (conflicts[classIndex][i] && timeSlot[i] == slot) {
  10.             return false;
  11.         }
  12.     }
  13.     return true;
  14. }
  15.  
  16. // Recursive utility to assign time slots
  17. bool scheduleClassesUtil(vector<vector<int>>& conflicts, int m, vector<int>& timeSlot, int classIndex) {
  18.     if (classIndex == conflicts.size()) {
  19.         return true; // All classes are scheduled
  20.     }
  21.  
  22.     for (int slot = 1; slot <= m; slot++) {
  23.         if (isSafe(classIndex, conflicts, timeSlot, slot)) {
  24.             timeSlot[classIndex] = slot;
  25.             if (scheduleClassesUtil(conflicts, m, timeSlot, classIndex + 1)) {
  26.                 return true;
  27.             }
  28.             timeSlot[classIndex] = 0; // Backtrack
  29.         }
  30.     }
  31.     return false;
  32. }
  33.  
  34. // Function to find minimum time slots required
  35. int findMinimumTimeSlots(vector<vector<int>>& conflicts) {
  36.     int m = 1;
  37.     while (true) {
  38.         vector<int> timeSlot(conflicts.size(), 0);
  39.         if (scheduleClassesUtil(conflicts, m, timeSlot, 0)) {
  40.             return m;
  41.         }
  42.         m++;
  43.     }
  44. }
  45.  
  46. // Main function
  47. int main() {
  48.     // Example conflict adjacency matrix
  49.     vector<vector<int>> conflicts = {
  50.         {0, 1, 0, 1, 0},
  51.         {1, 0, 1, 0, 1},
  52.         {0, 1, 0, 1, 0},
  53.         {1, 0, 1, 0, 1},
  54.         {0, 1, 0, 1, 0}
  55.     };
  56.  
  57.     int minTimeSlots = findMinimumTimeSlots(conflicts);
  58.     cout << "Minimum time slots required: " << minTimeSlots << endl;
  59.  
  60.     return 0;
  61. }
  62.  
Success #stdin #stdout 0.01s 5276KB
comments (?)
stdin
copy
stdout
copy 
Minimum time slots required: 2
https://ideone.com/XFZ1wD
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!