from typing import Collection
from typing import Tuple
from typing import List
from typing import Set


def book_meetings(
    meetings: Collection[Collection[int]],
) -> Tuple[List[List[int]], Collection[int]]:
    """Calculate meetings that maximizes non-conflicting attendees

    Non-conflicting means no attendee appears in multiple meetings.

    This is a single pass algorithm so it is not guaranteed to pick the
    maximum attendees in all cases.
    """
    # Parse list of meeting attendees with a set to ensure no duplicate attendees,
    # or duplicate meetings
    available_meetings = {frozenset(meeting) for meeting in meetings}

    # Sort meetings from largest to smallest so we book the largest meetings first
    sorted_meetings = sorted(available_meetings, key=lambda m: len(m), reverse=True)

    # Record the meetings and attendees that we book
    booked_meetings = []
    booked_attendees: Set[int] = set()

    # Book each meeting from largest to smallest, and skip meetings who have attendees
    # who have alreadly been booked.
    for meeting_attendees in sorted_meetings:
        if not meeting_attendees.intersection(booked_attendees):
            booked_attendees.update(meeting_attendees)
            booked_meetings.append(list(meeting_attendees))

    return booked_meetings, booked_attendees