# Minimum number of days required to schedule all exams

Given a graph consisting of **N** nodes, where each node represents an exam and a 2D array **Edges[][2]** such that each pair of the exam **(Edges[i][0], Edges[i][1])** denotes the edge between them, the task is to find the minimum number of days required to schedule all the exams such that no two exams connected via an edge are scheduled on the same day.

**Examples:**

Input:N = 5, E = 10, Edges[][] = {{0, 1}, {0, 2}, {0, 3}, {0, 4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}Output:5Explanation:In the above graph, all the nodes (representing exams) are connected to each other via a directed path. Therefore, the minimum number of days required to complete the exam is 5.

Input:N = 7, E = 12, Edges[][] = [{0, 1}, {0, 3}, {0, 4}, {0, 6}, {1, 2}, {1, 4}, {1, 6}, {2, 5}, {2, 6}, {3, 4}, {3, 5}, {4, 5}]Output:3

**Approach:** The given problem can be solved by using the concept of Graph Coloring. Although, the problem is NP complete, a good approximation is as follows.

- Create an adjacency matrix from the given Edges[][] of the graph.
- Initialize a vector of pairs, say
**vdegree[]**that stores the degree of each node with nodes. - Calculate the degree of each vertex and store it in the array
**vdegree[]**. - Arrange all vertices in
**vdegree[]**in descending order of degree. - Initialize two
**color[]**and**colored[]**to store colors used for coloring the vertices and whether a vertex has been colored or not. - Initialize two variables, say
**numvc**and**K**as**0**that keeps the track of the number of vertices colored and color number assigned to each node. - Iterate over the range
**[0, V]**using the variable**i**and perform the following steps:- If the value of
**numvc**is the same as the**V**, then break out of the loop as all vertices are colored. - If the current vertex is colored then continue the iteration.
- If the vertex is not colored, then color the vertex with color
**K**as**colored[vdegree[i]] = color[K]**and increment the value of**numvc**. - Iterate over the range
**[0, V]**, and if the current vertex is not colored and is not adjacent to node**i**, then color the current node with color**K**and increment the value of**numvc**. - Increment the value of
**K**by**1**.

- If the value of
- Sort the array colored[] in increasing order.
- After completing the above steps, print the value of the number of unique elements present in the array
**colored[]**as the minimum number of days.

Below is the implementation of the above approach:

## C++14

`// C++ program for the above approach` `#include <bits/stdc++.h>` `using` `namespace` `std;` `// Comparator function to sort the` `// vector of pairs in decreasing order` `bool` `compare(pair<` `int` `, ` `int` `> a,` ` ` `pair<` `int` `, ` `int` `> b)` `{` ` ` `// If the first values are the same` ` ` `if` `(a.first == b.first) {` ` ` `return` `(a.second < b.second);` ` ` `}` ` ` `// Otherwise` ` ` `else` `{` ` ` `return` `(a.first > b.first);` ` ` `}` `}` `// Function to add an undirected` `// edge between any pair of nodes` `void` `addEdge(vector<vector<` `int` `> >& adj,` ` ` `int` `u, ` `int` `v)` `{` ` ` `adj[u][v] = 1;` ` ` `adj[v][u] = 1;` `}` `// Function to find the minimum number` `// of days to schedule all the exams` `int` `minimumDays(` `int` `V, ` `int` `Edges[][2],` ` ` `int` `E)` `{` ` ` `// Stores the adjacency list of` ` ` `// the given graph` ` ` `vector<vector<` `int` `> > adj(` ` ` `V, vector<` `int` `>(V, 0));` ` ` `// Iterate over the edges` ` ` `for` `(` `int` `i = 0; i < E; i++) {` ` ` `int` `u = Edges[i][0];` ` ` `int` `v = Edges[i][1];` ` ` `// Add the edges between the` ` ` `// nodes u and v` ` ` `addEdge(adj, u, v);` ` ` `}` ` ` `// Initialize a vector of pair that` ` ` `// stores { degree, vertex }` ` ` `vector<pair<` `int` `, ` `int` `> > vdegree(V);` ` ` `for` `(` `int` `i = 0; i < V; i++) {` ` ` `// Degree of the node` ` ` `int` `degree = 0;` ` ` `vdegree[i].second = i;` ` ` `for` `(` `int` `j = 0; j < V; j++) {` ` ` `if` `(adj[i][j] != 0) {` ` ` `// Increment the degree` ` ` `degree++;` ` ` `}` ` ` `}` ` ` `// Update the degree of the` ` ` `// current node` ` ` `vdegree[i].first = degree;` ` ` `}` ` ` `// Sort to arrange all vertices` ` ` `// in descending order of degree` ` ` `sort(vdegree.begin(),` ` ` `vdegree.end(), compare);` ` ` `// Stores the vertices according` ` ` `// to degree in descending order` ` ` `int` `vorder[V];` ` ` `for` `(` `int` `i = 0; i < V; i++) {` ` ` `vorder[i] = vdegree[i].second;` ` ` `}` ` ` `// Stores the color of the all` ` ` `// the nodes` ` ` `int` `color[V];` ` ` `for` `(` `int` `i = 0; i < V; i++) {` ` ` `color[i] = i + 1;` ` ` `}` ` ` `int` `colored[V];` ` ` `// Initialize all vertices with` ` ` `// an invalid color 0` ` ` `memset` `(colored, 0, ` `sizeof` `(colored));` ` ` `// Keeps the track of number of` ` ` `// vertices colored` ` ` `int` `numvc = 0;` ` ` `// Track the different color` ` ` `// assigned` ` ` `int` `k = 0;` ` ` `for` `(` `int` `i = 0; i < V; i++) {` ` ` `// If all vertices are colored` ` ` `// then exit from the for loop` ` ` `if` `(numvc == V) {` ` ` `break` `;` ` ` `}` ` ` `// If vertex is already` ` ` `// colored, then continue` ` ` `if` `(colored[vorder[i]] != 0) {` ` ` `continue` `;` ` ` `}` ` ` `// If vertex not colored` ` ` `else` `{` ` ` `colored[vorder[i]] = color[k];` ` ` `// After coloring increase` ` ` `// the count of colored` ` ` `// vertex by 1` ` ` `numvc++;` ` ` `for` `(` `int` `j = 0; j < V; j++) {` ` ` `// If the current node` ` ` `// and its adjacent are` ` ` `// not colored` ` ` `if` `(colored[j] == 0` ` ` `&& adj[vorder[i]][j] == 0) {` ` ` `colored[j] = color[k];` ` ` `// Increment the count` ` ` `numvc++;` ` ` `}` ` ` `}` ` ` `// Increment k` ` ` `k++;` ` ` `}` ` ` `}` ` ` `// Sort the array` ` ` `sort(colored, colored + V);` ` ` `// Count of unique colors` ` ` `int` `unique_color = 1;` ` ` `// Count the number of unique` ` ` `// colors` ` ` `for` `(` `int` `i = 1; i < V; i++) {` ` ` `if` `(colored[i]` ` ` `!= colored[i - 1]) {` ` ` `unique_color++;` ` ` `}` ` ` `}` ` ` `// Return the number of days` ` ` `// to sechedule an exam` ` ` `return` `unique_color;` `}` `// Driver Code` `int` `main()` `{` ` ` `int` `V = 7, E = 12;` ` ` `int` `Edges[][2]` ` ` `= { { 0, 1 }, { 0, 3 }, { 0, 4 }, { 0, 6 }, { 1, 2 }, { 1, 4 }, { 1, 6 }, { 2, 5 }, { 2, 6 }, { 3, 4 }, { 3, 5 }, { 4, 5 } };` ` ` `cout << minimumDays(V, Edges, E);` ` ` `return` `0;` `}` |

## Python3

`# Python 3 program for the above approach` `# Comparator function to sort the` `# vector of pairs in decreasing order` `# Function to add an undirected` `# edge between any pair of nodes` `def` `addEdge(adj, u, v):` ` ` `adj[u][v] ` `=` `1` ` ` `adj[v][u] ` `=` `1` `# Function to find the minimum number` `# of days to schedule all the exams` `def` `minimumDays(V, Edges, E):` ` ` `# Stores the adjacency list of` ` ` `# the given graph` ` ` `adj ` `=` `[[` `0` `for` `i ` `in` `range` `(V)] ` `for` `j ` `in` `range` `(V)]` ` ` `# Iterate over the edges` ` ` `for` `i ` `in` `range` `(E):` ` ` `u ` `=` `Edges[i][` `0` `]` ` ` `v ` `=` `Edges[i][` `1` `]` ` ` `# Add the edges between the` ` ` `# nodes u and v` ` ` `addEdge(adj, u, v)` ` ` `# Initialize a vector of pair that` ` ` `# stores [degree, vertex }` ` ` `vdegree ` `=` `[[` `0` `,` `0` `] ` `for` `i ` `in` `range` `(V)]` ` ` `for` `i ` `in` `range` `(V):` ` ` `# Degree of the node` ` ` `degree ` `=` `0` ` ` `vdegree[i][` `1` `] ` `=` `i` ` ` `for` `j ` `in` `range` `(V):` ` ` `if` `(adj[i][j] !` `=` `0` `):` ` ` `# Increment the degree` ` ` `degree ` `+` `=` `1` ` ` `# Update the degree of the` ` ` `# current node` ` ` `vdegree[i][` `0` `] ` `=` `degree` ` ` `# Sort to arrange all vertices` ` ` `# in descending order of degree` ` ` `vdegree.sort(reverse` `=` `True` `)` ` ` `# Stores the vertices according` ` ` `# to degree in descending order` ` ` `vorder ` `=` `[` `0` `for` `i ` `in` `range` `(V)]` ` ` `for` `i ` `in` `range` `(V):` ` ` `vorder[i] ` `=` `vdegree[i][` `1` `]` ` ` `# Stores the color of the all` ` ` `# the nodes` ` ` `color ` `=` `[` `0` `for` `i ` `in` `range` `(V)]` ` ` `for` `i ` `in` `range` `(V):` ` ` `color[i] ` `=` `i ` `+` `1` ` ` `colored ` `=` `[` `0` `for` `i ` `in` `range` `(V)]` ` ` `# Keeps the track of number of` ` ` `# vertices colored` ` ` `numvc ` `=` `0` ` ` `# Track the different color` ` ` `# assigned` ` ` `k ` `=` `0` ` ` `for` `i ` `in` `range` `(V):` ` ` `# If all vertices are colored` ` ` `# then exit from the for loop` ` ` `if` `(numvc ` `=` `=` `V):` ` ` `break` ` ` `# If vertex is already` ` ` `# colored, then continue` ` ` `if` `(colored[vorder[i]] !` `=` `0` `):` ` ` `continue` ` ` `# If vertex not colored` ` ` `else` `:` ` ` `colored[vorder[i]] ` `=` `color[k]` ` ` `# After coloring increase` ` ` `# the count of colored` ` ` `# vertex by 1` ` ` `numvc ` `+` `=` `1` ` ` `for` `j ` `in` `range` `(V):` ` ` `# If the current node` ` ` `# and its adjacent are` ` ` `# not colored` ` ` `if` `(colored[j] ` `=` `=` `0` `and` `adj[vorder[i]][j] ` `=` `=` `0` `):` ` ` `colored[j] ` `=` `color[k]` ` ` `# Increment the count` ` ` `numvc ` `+` `=` `1` ` ` `# Increment k` ` ` `k ` `+` `=` `1` ` ` `# Sort the array` ` ` `colored.sort()` ` ` `# Count of unique colors` ` ` `unique_color ` `=` `1` ` ` `# Count the number of unique` ` ` `# colors` ` ` `for` `i ` `in` `range` `(` `1` `,V,` `1` `):` ` ` `if` `(colored[i] !` `=` `colored[i ` `-` `1` `]):` ` ` `unique_color ` `+` `=` `1` ` ` `# Return the number of days` ` ` `# to sechedule an exam` ` ` `return` `unique_color` `# Driver Code` `if` `__name__ ` `=` `=` `'__main__'` `:` ` ` `V ` `=` `7` ` ` `E ` `=` `12` ` ` `Edges ` `=` `[[` `0` `, ` `1` `], [` `0` `, ` `3` `], [` `0` `, ` `4` `], [` `0` `, ` `6` `], [` `1` `, ` `2` `], [` `1` `, ` `4` `], [` `1` `, ` `6` `], [` `2` `, ` `5` `], [` `2` `, ` `6` `], [` `3` `, ` `4` `], [` `3` `, ` `5` `], [` `4` `, ` `5` `] ]` ` ` `print` `(minimumDays(V, Edges, E))` ` ` ` ` `# This code is contributed by ipg2016107.` |

**Output:**

3

**Time Complexity:** O(N^{2}) **Auxiliary Space:** O(N)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the **DSA Self Paced Course** at a student-friendly price and become industry ready. To complete your preparation from learning a language to DS Algo and many more, please refer **Complete Interview Preparation Course****.**

In case you wish to attend **live classes **with experts, please refer **DSA Live Classes for Working Professionals **and **Competitive Programming Live for Students**.