The simple approach: store all booked intervals. For each new booking, check against all existing ones. If no overlap, add it. Time: per booking where is number of existing bookings. For total bookings, overall. Space: to store all bookings.
A better approach uses a balanced tree to store intervals sorted by start time. Binary search finds potential overlaps in . For now, the simple approach works for most constraints.