Preventing adjacent/overlapping entries with EXCLUDE in PostgreSQL

You can rewrite the exclude with the range type introduced in 9.2. Better yet, you could replace the two fields with a range. See "Constraints on Ranges" here, with an example that basically amounts to your use case:

http://www.postgresql.org/docs/current/static/rangetypes.html

Range types consist of lower and upper bound, and each can be included or excluded.
The canonical form (and default for range types) is to include the lower and exclude the upper bound.

Inclusive bounds '[]'

You could include lower and upper bound ([]), and enforce it with a CHECK constraint using range functions.

Then "adjacent" ranges overlap. Excluding overlapping ranges seems clear. There is a code example in the manual.

CREATE TABLE tbl (
   tbl_id serial PRIMARY KEY
 , tsr tsrange
 , CONSTRAINT tsr_no_overlap EXCLUDE USING gist (tsr WITH &&)
 , CONSTRAINT tsr_enforce_incl_bounds CHECK (lower_inc(tsr) AND upper_inc(tsr))  -- all bounds inclusive!
);

Only ranges with inclusive bounds are allowed:

INSERT INTO tbl(tsr) VALUES ('[2013-10-22 00:00, 2013-10-22 01:00]');

db<>fiddle here

Canonical bounds '[)'

Enforce [) bounds (including lower and excluding upper).

In addition, create another exclusion constraint employing the adjacent operator -|- to also exclude adjacent entries. Both are based on GiST indexes as GIN is currently not supported for this.

CREATE TABLE tbl (
   tbl_id serial PRIMARY KEY
 , tsr tsrange
 , CONSTRAINT tsr_no_overlap  EXCLUDE USING gist (tsr WITH &&)
 , CONSTRAINT tsr_no_adjacent EXCLUDE USING gist (tsr WITH -|-)
 , CONSTRAINT tsr_enforce_bounds CHECK (lower_inc(tsr) AND NOT upper_inc(tsr))
);

db<>fiddle here
_{Old sqlfiddle}

Unfortunately, this creates two identical GiST indexes to implement both exclusion constraints, where one would suffice, logically.