Agenda de reservas Datas de chegada e partida

Considere o seguinte...

DROP TABLE IF EXISTS my_table;

CREATE TABLE my_table
(book_id  INT NOT NULL AUTO_INCREMENT PRIMARY KEY
,arrive_date DATE NOT NULL
,depart_date DATE NOT NULL
);

INSERT INTO my_table VALUES
(1,'2015-07-20','2015-07-22'),
(2,'2015-07-22','2015-07-23'),
(3,'2015-07-19','2015-07-20');

SELECT * FROM my_table;
+---------+-------------+-------------+
| book_id | arrive_date | depart_date |
+---------+-------------+-------------+
|       1 | 2015-07-20  | 2015-07-22  |
|       2 | 2015-07-22  | 2015-07-23  |
|       3 | 2015-07-19  | 2015-07-20  |
+---------+-------------+-------------+

Então, os SELECTs podem ficar assim...

SELECT '2015-07-22','2015-07-24' 
  FROM (SELECT 1) x 
  LEFT 
  JOIN my_table y
    ON y.arrive_date < '2015-07-24' AND y.depart_date > '2015-07-22'
 WHERE y.book_id IS NULL 
 LIMIT 1;
Empty set (0.00 sec)

SELECT '2015-07-23','2015-07-24' 
  FROM (SELECT 1) x 
  LEFT 
  JOIN my_table y
    ON y.arrive_date < '2015-07-24' AND y.depart_date > '2015-07-23'
 WHERE y.book_id IS NULL 
 LIMIT 1;
+------------+------------+
| 2015-07-23 | 2015-07-24 |
+------------+------------+
| 2015-07-23 | 2015-07-24 |
+------------+------------+

...mas você não precisa verificá-los primeiro. Eu deliberadamente escrevi os SELECTs de forma que a verificação possa acontecer como parte do INSERT ...

INSERT INTO my_table (arrive_date,depart_date)
SELECT '2015-07-23','2015-07-24' 
  FROM (SELECT 1) x 
  LEFT 
  JOIN my_table y
    ON y.arrive_date < '2015-07-24' AND y.depart_date > '2015-07-23'
 WHERE y.book_id IS NULL 
 LIMIT 1;

SELECT * FROM my_table;
+---------+-------------+-------------+
| book_id | arrive_date | depart_date |
+---------+-------------+-------------+
|       1 | 2015-07-20  | 2015-07-22  |
|       2 | 2015-07-22  | 2015-07-23  |
|       3 | 2015-07-19  | 2015-07-20  |
|       4 | 2015-07-23  | 2015-07-24  |
+---------+-------------+-------------+

Na prática, e dependendo da experiência do usuário que você deseja fornecer, você pode querer executar primeiro os SELECTs, para que o usuário possa ver imediatamente quais datas não estão disponíveis, e depois executar os INSERTs na hora de fazer a reserva - para ter certeza de que ninguém pegou essas datas enquanto o usuário estava no meio da reserva.