What is the best way to solve Course Schedule?

The optimized O(n) approach using Graphs patterns is generally preferred.

상위 150개 인터뷰쉬움

코스 일정

'강좌 일정' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

수강해야 하는 총 numCourses 과정이 있으며 0부터 numCourses - 1까지 레이블이 지정됩니다. 전제 조건[i] = [ai, bi]는 ai 과정을 수강하려면 먼저 bi 과정을 수강해야 함을 나타내는 배열 전제 조건이 제공됩니다.

예를 들어, [0, 1] 쌍은 강좌 0을 수강하려면 먼저 강좌 1을 수강해야 함을 나타냅니다.

모든 과정을 완료할 수 있으면 True를 반환합니다. 그렇지 않으면 False를 반환합니다.

canFinish(numCourses: int, prerequisites: List[List[int]]) -> bool 함수를 작성하세요.

제약

•1 <= numCourses <= 2000
•0 <= len(prerequisites) <= 5000
•prerequisites[i].length == 2
•0 <= ai, bi < numCourses

예

Example 1

Input

numCourses = 2, prerequisites = [[1,0]]

Output

True

Explanation

To take course 1 you should have finished course 0. So it is possible.

Example 2

Input

numCourses = 2, prerequisites = [[1,0],[0,1]]

Output

False

Explanation

To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. This is a cycle and therefore impossible.

Need a Hint?

세트나 힙과 같은 그래프 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

그래프 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(n)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def can_finish_opt(numCourses, prerequisites):
    preMap = {i: [] for i in range(numCourses)}
    for crs, pre in prerequisites: preMap[crs].append(pre)
    visiting = set()
    def dfs(crs):
        if crs in visiting: return False
        if preMap[crs] == []: return True
        visiting.add(crs)
        for pre in preMap[crs]:
            if not dfs(pre): return False
        visiting.remove(crs)
        preMap[crs] = []
        return True
    for crs in range(numCourses):
        if not dfs(crs): return False
    return True

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def can_finish_brute(numCourses, prerequisites):
    adj = {i: [] for i in range(numCourses)}
    for crs, pre in prerequisites: adj[crs].append(pre)
    def has_cycle(crs, visited):
        if crs in visited: return True
        visited.add(crs)
        for pre in adj[crs]:
            if has_cycle(pre, visited): return True
        visited.remove(crs)
        return False
    for crs in range(numCourses):
        if has_cycle(crs, set()): return False
    return True