select 
a.datetime_start as user1start,a.datetime_end as user1end,b.datetime_start as user2start,b.datetime_end as user2end,case when a.datetime_start > b.datetime_start then a.datetime_start 
   else b.datetime_start end as avail_start,case when a.datetime_end>b.datetime_end then b.datetime_end 
   else a.datetime_end end as avail_end
from users a inner join users b on
a.datetime_start<=b.datetime_end and a.datetime_end>=b.datetime_start     
and  a.userid={user1} and b.userid={user2}

SQL FIDDLE HERE.

编辑：
要比较超过2个用户,请尝试以下内容：

select max(datetime_start) as avail_start,min(datetime_end) as avail_end
from(
        select *,@rn := CASE WHEN @prev_start <=datetime_end and @prev_end >=datetime_start THEN @rn ELSE @rn+1 END AS rn,@prev_start := datetime_start,@prev_end := datetime_end 
        from(
          select * from users2 m
          where exists ( select null 
                          from users2 o 
                           where o.datetime_start <= m.datetime_end and o.datetime_end >= m.datetime_start
                           and o.id <> m.id 
                        ) 
             and m.userid in (2,4,3,5)
           order by m.datetime_start) t,(SELECT @prev_start := -1,@rn := 1,@prev_end=-1) AS vars 
) c 
group by rn 
having count(rn)=4 ;

需要根据用户数更改(2,5)中的m.userid并使count(rn)= 4.

SQL FIDDLE HERE