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: 5
Explanation: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 arrays, say 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.
- 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; } |
Java
// Java program for the above approach import java.io.*; import java.util.*; public class GFG { // Comparator function to sort the // vector of pairs in decreasing order public static int compare(Pair<Integer, Integer> a, Pair<Integer, Integer> b) { // If the first values are the same if (a.first == b.first) { return (a.second < b.second) ? - 1 : 1 ; } // Otherwise else { return (a.first > b.first) ? - 1 : 1 ; } } // Function to add an undirected // edge between any pair of nodes static void addEdge(List<List<Integer>> adj, int u, int v) { adj.get(u).set(v, 1 ); adj.get(v).set(u, 1 ); } // Function to find the minimum number // of days to schedule all the exams static int minimumDays( int V, int [][] Edges, int E) { // Stores the adjacency list of // the given graph List<List<Integer> > adj = new ArrayList<>(V); for ( int i = 0 ; i < V; i++) { adj.add( new ArrayList<>(Collections.nCopies(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 } List<Pair<Integer, Integer>> vdegree = new ArrayList<>(V); for ( int i = 0 ; i < V; i++) { vdegree.add( new Pair<>( 0 , i)); } for ( int i = 0 ; i < V; i++) { // Degree of the node int degree = 0 ; vdegree.get(i).second = i; for ( int j = 0 ; j < V; j++) { if (adj.get(i).get(j) != 0 ) { // Increment the degree degree++; } } // Update the degree of the // current node vdegree.get(i).first = degree; } // Sort to arrange all vertices // in descending order of degree vdegree.sort((a, b) -> compare(a, b)); // Stores the vertices according // to degree in descending order int [] vorder = new int [V]; for ( int i = 0 ; i < V; i++) { vorder[i] = vdegree.get(i).second; } // Stores the color of the all // the nodes int [] color = new int [V]; for ( int i = 0 ; i < V; i++) { color[i] = i + 1 ; } int [] colored = new int [V]; // Initialize all vertices with // an invalid color 0 Arrays.fill(colored, 0 ); // 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.get(vorder[i]).get(j) == 0 ) { colored[j] = color[k]; // Increment the count numvc++; } } // Increment k k++; } } // Sort the array Arrays.sort(colored); // 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 // required to schedule all exams return unique_color; } public static void main(String[] args) { int V = 7 ; int E = 12 ; int 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 } }; System.out.println(minimumDays(V, Edges, E)); } } class Pair<L, R> { L first; R second; public Pair(L first, R second) { this .first = first; this .second = second; } } |
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. |
C#
using System; using System.Linq; class GFG { static void AddEdge( int [,] adj, int u, int v) { adj[u, v] = 1; adj[v, u] = 1; } static int MinimumDays( int V, int [][] Edges, int E) { int [,] adj = new int [V, V]; int [][] vdegree = new int [V][]; for ( int i = 0; i < V; i++) { vdegree[i] = new int [2] { 0, i }; for ( int j = 0; j < V; j++) { adj[i, j] = 0; } } for ( int i = 0; i < E; i++) { int u = Edges[i][0]; int v = Edges[i][1]; AddEdge(adj, u, v); } for ( int i = 0; i < V; i++) { int degree = 0; for ( int j = 0; j < V; j++) { if (adj[i, j] != 0) { degree++; } } vdegree[i][0] = degree; } vdegree = vdegree.OrderByDescending(x => x[0]).ToArray(); int [] vorder = new int [V]; for ( int i = 0; i < V; i++) { vorder[i] = vdegree[i][1]; } int [] color = new int [V]; for ( int i = 0; i < V; i++) { color[i] = i + 1; } int [] colored = new int [V]; int numvc = 0; int k = 0; for ( int i = 0; i < V; i++) { if (numvc == V) { break ; } if (colored[vorder[i]] != 0) { continue ; } else { colored[vorder[i]] = color[k]; numvc++; for ( int j = 0; j < V; j++) { if (colored[j] == 0 && adj[vorder[i], j] == 0) { colored[j] = color[k]; numvc++; } } k++; } } Array.Sort(colored); int unique_color = 1; for ( int i = 1; i < V; i++) { if (colored[i] != colored[i - 1]) { unique_color++; } } return unique_color; } static void Main( string [] args) { int V = 7; int E = 12; int [][] Edges = new int [12][] { new int [2] {0, 1}, new int [2] {0, 3}, new int [2] {0, 4}, new int [2] {0, 6}, new int [2] {1, 2}, new int [2] {1, 4}, new int [2] {1, 6}, new int [2] {2, 5}, new int [2] {2, 6}, new int [2] {3, 4}, new int [2] {3, 5}, new int [2] {4, 5}, }; Console.WriteLine(MinimumDays(V, Edges, E)); } }; |
Javascript
<script> // JavaScript program for the above approach // Comparator function to sort the // vector of pairs in decreasing order function compare(a,b) { // If the first values are the same if (a[0] == b[0]) { return (a[1] - b[1]); } // Otherwise else { return (a[0] - b[0]); } } // Function to add an undirected // edge between any pair of nodes function 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 function minimumDays(V,Edges,E) { // Stores the adjacency list of // the given graph let adj = new Array(V); for (let i=0;i<V;i++) adj[i] = new Array(V).fill(0); // Iterate over the edges for (let i = 0; i < E; i++) { let u = Edges[i][0]; let 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 } let vdegree = new Array(V); for (let i = 0; i < V; i++) { // Degree of the node let degree = 0; vdegree[i] = new Array(2); vdegree[i][1] = i; for (let 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 vdegree.sort(compare); // Stores the vertices according // to degree in descending order let vorder = new Array(V); for (let i = 0; i < V; i++) { vorder[i] = vdegree[i][1]; } // Stores the color of the all // the nodes let color = new Array(V); for (let i = 0; i < V; i++) { color[i] = i + 1; } // Initialize all vertices with // an invalid color 0 let colored = new Array(V).fill(0); // Keeps the track of number of // vertices colored let numvc = 0; // Track the different color // assigned let k = 0; for (let 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 (let 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 colored.sort(); // Count of unique colors let unique_color = 1; // Count the number of unique // colors for (let 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 let V = 7, E = 12; let 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 ] ]; document.write(minimumDays(V, Edges, E), "</br>" ); // This code is contributed by shinjanpatra </script> |
3
Time Complexity: O(N2)
Auxiliary Space: O(N)
Contact Us