Retrieving with an Xpath should do the trick for you.
You’ll need to retrieve any objects where your new object’s start date sits between the start date and end date.
Something like this:
[Start Date<= $<Your Object>/StartDate]
[EndDate >= $<Your Object>/StartDate]
Then do a check on the list. If it’s empty, then nothing continue with the booking, if not show the error.