707516. Course Schedule
Course Schedule
Slug: course-schedule Difficulty: Medium Id: 707516 Topic Tags: DFS, Graph, BFS, Data Structures, Algorithms Company Tags: Google
Summary
The Course Schedule problem is a graph-based algorithmic problem where you are given a set of courses and their prerequisites. Your task is to determine if it's possible to schedule all the courses in a valid order. This problem involves graph traversal techniques such as DFS and BFS.
Detailed Explanation
Given a set of courses with their prerequisites, we need to find out whether it's possible to schedule all the courses in a valid order or not. A course can only be scheduled after its prerequisite has been completed. We can model this situation using a directed graph where each course is a node and the edges represent the dependencies between the courses.
One way to approach this problem is by using DFS or BFS algorithms to traverse the graph. The idea is to start from an arbitrary course (or node) and try to schedule all its prerequisites first. If we can successfully schedule all the prerequisites, then we can move on to the next level of courses that have these prerequisites as their prerequisites.
Here's a step-by-step breakdown of the solution:
- Create a graph using adjacency list representation where each node represents a course and the edges represent the dependencies between the courses.
- Initialize an empty stack or queue to store the courses that have been scheduled successfully.
- Start from an arbitrary course (or node) in the graph.
- If the current course has prerequisites, try to schedule all its prerequisites first using DFS or BFS algorithm.
- Once all the prerequisites of the current course have been scheduled successfully, add it to the stack or queue.
- Repeat steps 3-5 until all courses have been scheduled or a cycle is detected (i.e., a course that has already been scheduled becomes a prerequisite for another course).
- If all courses have been scheduled successfully without detecting any cycles, then it's possible to schedule all the courses in a valid order.
Time complexity: O(V + E) where V is the number of vertices (courses) and E is the number of edges (prerequisites).
Space complexity: O(V) for storing the graph and the stack or queue used for scheduling.
Optimized Solutions
Java
import java.util.*;
class Course {
int id;
List<Course> prerequisites = new ArrayList<>();
}
public class Solution {
public boolean isPossible(int numCourses, int[][] prerequisites) {
int V = numCourses;
Graph graph = new Graph(V);
for (int i = 0; i < prerequisites.length; i++) {
Course course = graph.getCourse(prerequisites[i][0]);
course.prerequisites.add(graph.getCourse(prerequisites[i][1]));
}
boolean[] visited = new boolean[V];
for (int i = 0; i < V; i++) {
if (!dfs(i, visited, graph)) return false;
}
return true;
}
private boolean dfs(int node, boolean[] visited, Graph graph) {
if (visited[node]) return false;
visited[node] = true;
for (Course course : graph.getCourse(node).prerequisites) {
if (!dfs(course.id, visited, graph)) return false;
}
return true;
}
class Graph {
Map<Integer, Course> courses = new HashMap<>();
public Graph(int V) {
for (int i = 0; i < V; i++) {
courses.put(i, new Course());
}
}
public Course getCourse(int id) {
return courses.get(id);
}
}
}