Solve meeting-room scheduling and shortest paths

Problem Statement

You are tasked with scheduling a set of meetings in a single conference room. Each meeting has a unique ID, a start time, and an end time. Additionally, some meetings have 'dependency' constraints: if meeting A is a prerequisite for meeting B, meeting B cannot start until meeting A has finished.

Task 1: Scheduling

Given a list of meetings (id, start, end), determine the minimum number of rooms required to host all meetings without overlap. If a room becomes free at time T, a new meeting can start at time T.

Task 2: Critical Path

Given a list of dependencies (prerequisite_id, meeting_id), identify the 'critical path'—the sequence of dependent meetings that results in the longest total duration. If there are no dependencies, return the duration of the longest single meeting.

Function Signature

def solve_scheduling(meetings, dependencies):
    # meetings: List of tuples (id, start, end)
    # dependencies: List of tuples (prereq_id, meeting_id)
    # Return: (min_rooms_needed, max_dependency_duration)

Constraints

• 1 <= len(meetings) <= 10^4
• 0 <= start < end <= 10^9
• dependencies form a Directed Acyclic Graph (DAG).

Example

Input: meetings = [(1, 0, 5), (2, 2, 6), (3, 7, 10)] dependencies = [(1, 2)]

Output: (2, 9)

Explanation:

• Room 1 hosts meeting 1 (0-5) and meeting 3 (7-10). Room 2 hosts meeting 2 (2-6). Total 2 rooms.
• Dependency 1 -> 2: Meeting 1 duration (5) + Meeting 2 duration (4) = 9. Max path is 9.

Edge Cases

• Empty meetings or dependencies.
• Meetings with no dependencies.
• Disconnected components in the dependency graph.