scheduler.rb

require 'time'
require 'forwardable'

module Schedule
  class Item
    attr_reader :id, :from, :to, :count_per_hour
    attr_reader :from_sec, :to_sec, :layout, :span
    attr_accessor :place

    extend Forwardable
    def_delegator :layout, :size

    def initialize(id, from, to, count_per_hour)
      @id, @from, @to, @count_per_hour = id, from, to, count_per_hour
      @from_sec = @from.hour * 3600 + @from.min * 60 * @from.sec
      @to_sec = @to.hour * 3600 + @to.min * 60 + @to.sec

      @span = 3600 / count_per_hour
      @layout = (@from_sec...@to_sec).step(@span).map{|sec|
        (sec - @from_sec) / DEFAULT_SPAN * DEFAULT_SPAN # пока — округляем время начала до минуты
      }
    end

    def has_place?
      !@place.nil?
    end

    def period
      @to_sec - @from_sec
    end
  end

  DEFAULT_SPAN = 60

  class Scheduler
    def initialize(items)
      # первыми пытаемся разложить самые частые (результат экспериментов — иначе они могут не лечь вообще)
      # ...и самые длинные из них
      @items = items.sort_by{|i| [i.span, -i.period]}
    end

    LayoutError = Class.new(RuntimeError)

    def layout!
      @board = Board.new
      fails = []

      begin
        while !place_item(0) && !@items.empty?
          fails << @items.pop # если не получилось разложить все — раскладываем без последнего
        end
      rescue LayoutError => e
      end

      @items.select(&:has_place?).map { |i|
        i.layout.map { |sec| [i.place + sec, i.id] }
      }.flatten(1).sort.each do |sec, id|
        puts '%02i:%02i:%02i - %s' % [sec / 3600, sec / 60 % 60, sec % 60, id]
      end

      fails.concat(@items.reject(&:has_place?)).uniq.sort_by(&:id)
      puts "No place for: #{fails.map(&:id)}" unless fails.empty?
    end

    def place_item(i)
      return true if i >= @items.count

      item = @items[i]

      if @board.free_places_between(item.from_sec, item.to_sec) < item.size
        # предполагаем, что если не вмещается на доске вообще — не вместится ни он, ни следующие, как его не двигай
        # возможно, слишком сильное предположение, проверить.
        raise LayoutError, "Can't layout #{item.id}"
      end

      (item.span / DEFAULT_SPAN).times.each do |shift|
        place = item.from_sec + shift * DEFAULT_SPAN
        next unless @board.place(item, place)
        return true if place_item(i + 1)
        @board.remove(item, place)
      end

      false
    end
  end

  class Board
    def initialize
      @board = Array.new(24*60*60)
    end

    extend Forwardable
    def_delegator :@board, :size

    def place(item, place)
      return false unless can_be_placed?(item, place)
      item.layout.each { |shift|
        DEFAULT_SPAN.times.each { |sec| @board[place+shift+sec] = item.id }
      }
      item.place = place
    end

    def remove(item, place)
      item.layout.each { |shift|
        DEFAULT_SPAN.times.each { |sec| @board[place+shift+sec] = nil }
      }
      item.place = nil
    end

    def free_places_between(from, to)
      @board[from..to].select(&:nil?).count
    end

    def can_be_placed?(item, place)
      item.layout.all? { |shift|
        DEFAULT_SPAN.times.all? { |sec| @board[place+shift+sec].nil? }
      }
    end
  end
end

test.rb

require_relative 'scheduler'

def make_item(idx, f,t,c)
  Schedule::Item.new(idx, Time.parse(f), Time.parse(t), c)
end

bar = [
  ['11:00', '16:00', 6],
  ['11:00', '23:00', 4],
  ['11:00', '23:00', 4],
  ['16:00', '23:00', 6],
  ['16:00', '23:00', 4],
  ['11:00', '23:00', 2],
  ['11:00', '23:00', 4],
  ['11:00', '23:00', 6],
  ['11:00', '23:00', 10],
  ['11:00', '14:00', 2],
  ['11:00', '14:00', 2],
  ['18:00', '23:00', 2],
  ['15:00', '17:00', 4],
  ['19:00', '23:00', 2],
  ['20:00', '23:00', 4]
].map.with_index(1) { |i, idx| make_item(idx, *i) }

cafe2 = [
  ['09:00', '11:00', 8],
  ['15:00', '17:00', 8],
  ['09:00', '20:00', 4],
  ['09:00', '11:00', 6],
  ['15:00', '18:00', 6],
  ['12:00', '15:00', 4],
  ['18:00', '20:00', 7],
  ['11:00', '18:00', 3],
  ['15:00', '17:00', 7],
  ['18:00', '20:00', 5],
  ['09:00', '20:00', 2],
  ['10:00', '14:30', 3],
  ['17:45', '20:00', 3],
  ['16:45', '19:15', 4],
  ['12:30', '16:50', 4]
].map.with_index(1) { |i, idx| make_item(idx, *i) } # 28 сек, не удаётся раскидать

cafe = [
  ['09:00', '11:00', 6],
  ['09:00', '20:00', 4],
  ['09:00', '11:00', 6],
  ['12:00', '15:00', 6],
  ['11:00', '18:00', 4],
  ['15:00', '17:00', 7],
  ['18:00', '20:00', 6],
  ['09:00', '20:00', 2],
  ['09:00', '13:30', 3],
  ['16:45', '19:15', 5],
  ['12:30', '16:50', 3]
].map.with_index(1) { |i, idx| make_item(idx, *i) } # 16 сек, не удаётся раскидать

restaurant = [
  ['09:00', '13:30', 4],
  ['16:00', '18:00', 4],
  ['09:00', '13:30', 6],
  ['09:00', '13:30', 7],
  ['16:00', '20:00', 7],
  ['13:00', '15:00', 5],
  ['19:00', '20:00', 5],
  ['13:30', '16:00', 3],
  ['13:30', '23:00', 5],
  ['12:00', '20:00', 1],
  ['18:00', '21:00', 9],
  ['13:00', '16:55', 8],
  ['12:30', '16:50', 4],
  ['19:00', '23:00', 4],
  ['17:00', '21:00', 6],
  ['17:00', '21:30', 3],
  ['17:30', '22:00', 3]
].map.with_index(1) { |i, idx| make_item(idx, *i) } # не удаётся раскидать

supermarket = [
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4],
  ['09:00', '23:00', 4]
].map.with_index(1) { |i, idx| make_item(idx, *i) } # не удаётся раскидать, через несколько минут прибил процесс т.к. надоело ждать :)

times = [bar, cafe, cafe2, restaurant, supermarket].map { |items|
  s = Time.now
  Schedule::Scheduler.new(items).layout!
  Time.now - s
}

p times