Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$
(From your notations, I assume the intervals are all discrete as otherwise some of the $J_n$ would not be closed. Furthermore, the length of the intervals would not be $b_n-a_n+1$ so I'm fairly certain that assumption is safe. If however that was not your intention, it should be straightforward enough to adapt the algorithm to the continuous case).


Consider all intervals $(I_n=[\![s_n,e_n]\!])_{0\leq n&lt;p}$, and sort them by increasing start time $s_n$, breaking ties arbitrarily  [time $\mathcal{O}(p\cdot \log p)$]
Build a stack containing only the first interval (i.e. the one with the smallest start). For each subsequent interval: if [the interval doesn't overlap with the head of the stack] then [push it] else [merge it with the head of the stack] [time $\mathcal{O}(p)$]


What we've done here is merge the intervals $(I_n)_n$ so as to rewrite $\bigcup I_n$ as an ordered stack of disjoint intervals. We shall call these intervals $(\tilde{I}_n=[\![\tilde{s}_n,\tilde{b}_n]\!])_n$

Now iterate linearly through the stack to find the largest interval separating two successive intervals on the stack (without forgetting the two intervals $[\![0,\tilde{s}_0[\![$ and $]\!]\tilde{s}_{-1},L]\!]$) [time $\mathcal{O}(p)$]

Overall the runtime is $\mathcal{O}(p\cdot \log p)$.