Se você estiver disposto a olhar apenas uma semana de cada vez, poderá canonizar todos os horários de abertura/fechamento para definir números de minutos desde o início da semana, digamos, domingo 0 horas. Para cada loja, você cria um número de tuplas no formato [startTime, endTime, storeId]. (Para horas que abrangessem a meia-noite de domingo, você teria que criar duas tuplas, uma indo até o final da semana e outra começando no início da semana). Esse conjunto de tuplas seria indexado (digamos, com uma árvore que você pré-processaria) em startTime e endTime. As tuplas não devem ser tão grandes:há apenas ~10k minutos em uma semana, que podem caber em 2 bytes. Essa estrutura seria graciosa dentro de uma tabela MySQL com índices apropriados e seria muito resiliente a inserções e exclusões constantes de registros à medida que as informações fossem alteradas. Sua consulta seria simplesmente "select storeId where startTime <=time and endtime>=time", onde time era os minutos canonizados desde a meia-noite de domingo.

Se as informações não mudam com muita frequência e você deseja que as pesquisas sejam muito rápidas, você pode resolver todas as consultas possíveis antecipadamente e armazenar em cache os resultados. Por exemplo, há apenas 672 períodos de quarto de hora em uma semana. Com uma lista de empresas, cada uma com uma lista de horários de abertura e fechamento, como a solução de Brandon Rhodes, você pode simplesmente iterar a cada período de 15 minutos em uma semana, descobrir quem está aberto e armazenar a resposta em uma tabela de pesquisa ou lista na memória.