algorithm - イベントのタイムテーブル

Question

私には次の仕事があります。24時間の時刻表があります。また、固定長のイベントもあります。事前定義された長さ（たとえば、1時間25分）の新しいイベントがあります。タスクは、このタスクを1日に何回挿入できるかを知ることです（このタスクは他のイベントと交差してはなりません）。

Answer 1

私たちの質問は少し単純化されていると思われるかもしれないので、答えも (Ruby で) 単純化してみましょう。

#! /usr/bin/ruby
DAY_START = 0
DAY_END = 24*60
# now, busy periods as array of size-2 arrays:
BUSY_PERIODS = [[9*60, 9*60+30], [18*60+30, 20*60]]
ADDITIONAL_EVENT_LENGTH = 1*60 + 25   # that is, 1 hour and  25 minutes
# in this simple program,
# time will be expressed as a number of minutes of the day
# for more advanced use, try to use "Time" class

# now let define a function to compute the list of free periods
# from a given list of busy periods:
def compute_free_periods( list_of_events )
  # at the begining of the calculation, our whole day is assumed free:
  free_periods = Array[ [ DAY_START, DAY_END] ]
  # now, one by one, let us take away the busy periods:
  list_of_events.each_with_object free_periods do | busy_period, free_periods |
    # we use 'each_with_object' version of 'each' enumerator
    # list of free_periods is passed in as an external object
    # so that we can gradually take each busy period away from it

    # let us first note the end time for the last free period
    # ( [-1] refers to the last element of the list of free periods,
    # subsequent [1] to the second element of the size-2 array )
    last_free_period_end = free_periods[-1][1]

    # and now, let us split this last free period into two by the
    # current busy period (busy periods assumed non-overlapping and
    # sorted in ascending order)

    # first, end time of the last free period is set to the beginning
    # of the busy period that we consider in this iteration:
    free_periods[-1][1] = busy_period[0]

    # then, additional free period is appended to the list of
    # free periods usind << operator, starting when the busy period ends:
    free_periods << [ busy_period[1], last_free_period_end ]
  end
end

# now, let us use the function we just defined:
free_periods = compute_free_periods( BUSY_PERIODS )

# Now, for each free period we will count how many times we can stuff
# in the desired additional event:
free_period_capacities = free_periods.map { |free_period|
  # we are using map function for this, which will return
  # an array of the same length as free_periods, having
  # performed prescribed modifications on each element:

  # first, we calculate how many minutes a free period has
  period_length = free_period[1] - free_period[0]
  # then, we will use whole-number division to get the number
  # of additional events that can fit in:
  period_length / ADDITIONAL_EVENT_LENGTH
  # (in Ruby, whole number division is the default behavior of / operator)
}

# and finally, we sum up the free period capacities for our new event:
total_events_possible = free_period_capacities.reduce( :+ )
# (summing is done elegantly by using reduce function with + operator)

# the last remaining thing we can do to consider program finished is to
puts total_events_possible # print the result on the screen

コメントを削除して短くすると、プログラムは非常に短くなります。

#! /usr/bin/ruby
DAY_START, DAY_END = 0, 24*60
BUSY_PERIODS = [[9*60, 9*60+30], [18*60+30, 20*60]]
ADDITIONAL_EVENT_LENGTH = 1*60 + 25

def compute_free_periods( list_of_events )
  free_periods = Array[ [ DAY_START, DAY_END] ]
  list_of_events.each_with_object free_periods do | busy_period, free_periods |
    last_free_period_end = free_periods[-1][1]
    free_periods[-1][1] = busy_period[0]
    free_periods << [ busy_period[1], last_free_period_end ] end
end

free_periods = compute_free_periods( BUSY_PERIODS )
free_period_capacities = free_periods.map { |free_period|
  period_length = free_period[1] - free_period[0]
  period_length / ADDITIONAL_EVENT_LENGTH }
puts ( total_events_possible = free_period_capacities.reduce( :+ ) )

ご覧のとおり、アルゴリズムはそれほど多くありません。単純なコーディング。ピックアップ例えば。Ole Foul Zed の教科書Ruby The Hard Wayを学び、演習 0 から最後まで読み始めます。または、Pythonなどの他の言語を使用することもできます。オレ・ゼッドには教育の才能があります。この経験に感謝するなら、電子ブックとして購入することを忘れないでください。