from typing import List, Dict, Set, Optional
from dataclasses import dataclass, field
from datetime import datetime
import uuid

@dataclass
class Session:
    """Represents a conference session with scheduling details."""
    title: str
    start_time: int  # Hour in 24-hour format
    end_time: int
    capacity: int
    session_id: str = field(default_factory=lambda: str(uuid.uuid4()))
    room: Optional[int] = None
    day: Optional[int] = None
    registered_attendees: Set[str] = field(default_factory=set)
    waitlist: List[str] = field(default_factory=list)
    
    def has_conflict(self, other: 'Session') -> bool:
        """Check if this session overlaps with another session."""
        # Sessions conflict if they overlap in time
        return self.start_time < other.end_time and other.start_time < self.end_time
    
    def is_full(self) -> bool:
        """Check if session is at capacity."""
        return len(self.registered_attendees) >= self.capacity
    
    def add_attendee(self, attendee_id: str) -> bool:
        """Add an attendee to the session or waitlist."""
        if attendee_id in self.registered_attendees:
            return False
        
        if self.is_full():
            if attendee_id not in self.waitlist:
                self.waitlist.append(attendee_id)
            return False
        
        self.registered_attendees.add(attendee_id)
        return True
    
    def remove_attendee(self, attendee_id: str) -> bool:
        """Remove an attendee and promote from waitlist if available."""
        if attendee_id not in self.registered_attendees:
            return False
        
        self.registered_attendees.remove(attendee_id)
        
        # Promote from waitlist
        if self.waitlist:
            next_attendee = self.waitlist.pop(0)
            self.registered_attendees.add(next_attendee)
        
        return True


@dataclass
class Attendee:
    """Represents a conference attendee."""
    name: str
    email: str
    attendee_id: str = field(default_factory=lambda: str(uuid.uuid4()))
    registered_sessions: Set[str] = field(default_factory=set)
    
    def can_attend(self, session: Session, all_sessions: Dict[str, Session]) -> bool:
        """Check if attendee can attend a session without conflicts."""
        for session_id in self.registered_sessions:
            existing_session = all_sessions.get(session_id)
            if existing_session and existing_session.has_conflict(session):
                # Check if sessions are on the same day
                if existing_session.day == session.day:
                    return False
        return True


class Conference:
    """Main conference management system."""
    
    def __init__(self, name: str, num_rooms: int, num_days: int = 1):
        self.name = name
        self.num_rooms = num_rooms
        self.num_days = num_days
        self.sessions: Dict[str, Session] = {}
        self.attendees: Dict[str, Attendee] = {}
        
        # Index sessions by room and day for efficient conflict checking
        # Structure: {day: {room: [sessions sorted by start_time]}}
        self.room_schedule: Dict[int, Dict[int, List[Session]]] = {}
        for day in range(1, num_days + 1):
            self.room_schedule[day] = {room: [] for room in range(1, num_rooms + 1)}
    
    def add_session(self, session: Session, room: int, day: int) -> bool:
        """
        Add a session to the conference schedule.
        Returns True if successful, False if there's a conflict.
        
        Time Complexity: O(n) where n is the number of sessions in the room
        Space Complexity: O(1)
        """
        if room < 1 or room > self.num_rooms:
            return False
        
        if day < 1 or day > self.num_days:
            return False
        
        # Check for conflicts with existing sessions in the same room
        for existing_session in self.room_schedule[day][room]:
            if session.has_conflict(existing_session):
                return False
        
        # Assign room and day to session
        session.room = room
        session.day = day
        
        # Add to sessions dictionary
        self.sessions[session.session_id] = session
        
        # Add to room schedule (maintain sorted order by start time)
        room_sessions = self.room_schedule[day][room]
        # Insert in sorted position
        inserted = False
        for i, s in enumerate(room_sessions):
            if session.start_time < s.start_time:
                room_sessions.insert(i, session)
                inserted = True
                break
        if not inserted:
            room_sessions.append(session)
        
        return True
    
    def register_attendee(self, attendee: Attendee, session_id: str) -> tuple[bool, str]:
        """
        Register an attendee for a session.
        Returns (success, message) tuple.
        
        Time Complexity: O(m) where m is the number of sessions attendee is registered for
        Space Complexity: O(1)
        """
        # Get or create attendee record
        if attendee.attendee_id not in self.attendees:
            self.attendees[attendee.attendee_id] = attendee
        
        session = self.sessions.get(session_id)
        if not session:
            return False, "Session not found"
        
        # Check if attendee can attend (no conflicts)
        if not attendee.can_attend(session, self.sessions):
            return False, "Schedule conflict with existing session"
        
        # Try to add attendee to session
        if session.add_attendee(attendee.attendee_id):
            attendee.registered_sessions.add(session_id)
            return True, "Successfully registered"
        else:
            return False, "Session is full (added to waitlist)"
    
    def unregister_attendee(self, attendee_id: str, session_id: str) -> bool:
        """
        Unregister an attendee from a session.
        
        Time Complexity: O(1)
        Space Complexity: O(1)
        """
        attendee = self.attendees.get(attendee_id)
        session = self.sessions.get(session_id)
        
        if not attendee or not session:
            return False
        
        if session.remove_attendee(attendee_id):
            attendee.registered_sessions.discard(session_id)
            return True
        
        return False
    
    def get_schedule(self, day: int, room: Optional[int] = None) -> List[Session]:
        """
        Get schedule for a specific day and optionally a specific room.
        
        Time Complexity: O(r * s) where r is rooms and s is sessions per room
        Space Complexity: O(total sessions returned)
        """
        if day not in self.room_schedule:
            return []
        
        if room:
            return self.room_schedule[day].get(room, [])
        
        # Return all sessions for the day across all rooms
        all_sessions = []
        for room_sessions in self.room_schedule[day].values():
            all_sessions.extend(room_sessions)
        
        # Sort by start time
        return sorted(all_sessions, key=lambda s: s.start_time)
    
    def get_attendee_schedule(self, attendee_id: str) -> List[Session]:
        """
        Get all sessions an attendee is registered for.
        
        Time Complexity: O(m) where m is number of sessions attendee registered for
        Space Complexity: O(m)
        """
        attendee = self.attendees.get(attendee_id)
        if not attendee:
            return []
        
        return [self.sessions[sid] for sid in attendee.registered_sessions 
                if sid in self.sessions]
    
    def get_session_attendees(self, session_id: str) -> List[Attendee]:
        """
        Get all attendees registered for a session.
        
        Time Complexity: O(a) where a is number of attendees in session
        Space Complexity: O(a)
        """
        session = self.sessions.get(session_id)
        if not session:
            return []
        
        return [self.attendees[aid] for aid in session.registered_attendees 
                if aid in self.attendees]


# Example usage demonstrating the system
def main():
    # Create a 3-day conference with 5 rooms
    conference = Conference("TechConf 2024", num_rooms=5, num_days=3)
    
    # Create sessions
    sessions = [
        Session("Python Mastery", 9, 10, 100),
        Session("Cloud Native Architecture", 10, 12, 150),
        Session("Machine Learning at Scale", 9, 11, 80),
        Session("DevOps Automation", 13, 15, 120),
        Session("Security Best Practices", 15, 17, 100),
    ]
    
    # Schedule sessions
    conference.add_session(sessions[0], room=1, day=1)  # Python 9-10, Room 1
    conference.add_session(sessions[1], room=1, day=1)  # Cloud 10-12, Room 1 (OK)
    conference.add_session(sessions[2], room=2, day=1)  # ML 9-11, Room 2
    conference.add_session(sessions[3], room=1, day=2)  # DevOps 13-15, Room 1
    conference.add_session(sessions[4], room=2, day=2)  # Security 15-17, Room 2
    
    # Create attendees
    alice = Attendee("Alice Johnson", "alice@example.com")
    bob = Attendee("Bob Smith", "bob@example.com")
    
    # Register attendees
    success, msg = conference.register_attendee(alice, sessions[0].session_id)
    print(f"Alice -> Python: {msg}")
    
    success, msg = conference.register_attendee(alice, sessions[1].session_id)
    print(f"Alice -> Cloud: {msg}")
    
    # This should fail due to time conflict
    success, msg = conference.register_attendee(alice, sessions[2].session_id)
    print(f"Alice -> ML: {msg}")
    
    # Get schedules
    day1_schedule = conference.get_schedule(day=1)
    print(f"\nDay 1 has {len(day1_schedule)} sessions")
    
    alice_schedule = conference.get_attendee_schedule(alice.attendee_id)
    print(f"Alice is registered for {len(alice_schedule)} sessions")


if __name__ == "__main__":
    main()