我的幼稚解决方案（尚未优化），基本上我的想法是我将输入数组平面映射到一个数组中，每个元素是一对[time arrive/leave, friend index]，然后我将根据时间对该数组进行排序（不管到达或离开），如果两对都有相同的时间，然后我将比较恶魔索引的到达时间。最后，我遍历排序的数组并评估minimum free chair index每一步，每当我遇到targetFriendi 时都会返回minimum free chair index。
# @param {Integer[][]} times
# @param {Integer} target_friend
# @return {Integer}
def smallest_chair(times, target_friend)
# times = [[1,2],[4,7],[2,4]]
# targetFriend = 1
sit_times = times.each_with_index.inject([]) { |combi, (time, index)|
combi += [[time.first, index], [time.last, index]]
}
# [[1, 0], [2, 0], [4, 1], [7, 1], [2, 2], [4, 2]]
sit_times.sort! {|x, y|
c = x[0] <=> y[0]
# [[1, 0], [2, 0], [2, 2], [4, 1], [4, 2], [7, 1]]
c = times[x[1]][0] <=> times[y[1]][0] if c == 0
# [[1, 0], [2, 0], [2, 2], [4, 2], [4, 1], [7, 1]]
c
}
chairs = {} # to mark time of friend
occupied = Array.new(times.size, 0) # occupied chair: 1, otherwise: 0
min_free = 0 # current minimum not occupied chair
sit_times.each do |time, friend_index|
if target_friend == friend_index # check
return min_free
end
sit = chairs[friend_index]
if sit # leave
occupied[sit] = 0
chairs[friend_index] = nil
min_free = sit if min_free > sit
else # arrive
chairs[friend_index] = min_free
occupied[min_free] = 1
min_free += 1 until occupied[min_free] == 0 # re-calculate
end
end
end
注意：代码在 leetcode 上通过了测试用例，但性能不佳。
这里的更新
是更好的版本，使用 3 个优先级队列，一个用于到达时间，一个用于离开时间，最后一个用于椅子。
优先队列类
class PriorityQueue
attr_reader :length
def initialize(opts={}, &comparator)
order_opt = opts.fetch(:order, :asc)
@order = order_opt == :asc ? -1 : 1
@comparator = comparator
@items = [nil]
@length = 0
end
def push(item)
@items << item
@length += 1
swim(@length)
true
end
def pop
return nil if empty?
swap(1, @length) if @length > 1
@length -= 1
sink(1) if @length > 0
@items.pop
end
def empty?
@length == 0
end
def swap(i, j)
temp = @items[i]
@items[i] = @items[j]
@items[j] = temp
end
def in_order?(i, j)
x = @items[i]
y = @items[j]
order = @comparator.nil? ? (x <=> y) : @comparator.call(x, y)
order == @order
end
def swim(from)
while (up = from / 2) >= 1
break if in_order?(up, from)
swap(up, from)
from = up
end
end
def sink(from)
while (down = from * 2) <= @length
down += 1 if down < @length && in_order?(down + 1, down)
break if in_order?(from, down)
swap(down, from)
from = down
end
end
end
具有优先级队列的最小椅子（请注意，我发现使用sort的到达时间比队列快，但基本上这个想法是相同的）
def smallest_chair_pq(times, target_friend)
# a_pq = PriorityQueue.new { |x, y|
# x[0] <=> y[0]
# }
#
# times.each do |t|
# a_pq.push(t)
# end
# sort arrive times is faster than a priority queue
a_pq = times.sort_by(&:first).reverse
# leave times queue
l_pq = PriorityQueue.new { |x, y|
c = x[0] <=> y[0]
c = x[1] <=> y[1] if c == 0
c
}
# chair-indexes queue
# consider case a friend come in at arrive-time at1
# and there's a range chairs with leave times in range lm <= at1 <= ln
# that mean that friend could pick one of those chairs
# and according this problem requirement, should pick the minimun chair index
c_pq = PriorityQueue.new
target_time = times[target_friend][0]
last_chair_index = 0
until a_pq.empty?
a_top = a_pq.pop
arrive_time = a_top.first
if l_pq.empty?
return 0 if arrive_time == target_time
l_pq.push([a_top.last, 0])
else
l_top = l_pq.pop
if l_top.first <= arrive_time
c_pq.push(l_top.last)
until (l_ntop = l_pq.pop).nil? || arrive_time < l_ntop.first
c_pq.push(l_ntop.last)
end
l_pq.push(l_ntop) unless l_ntop.nil?
min_chair_index = c_pq.pop
return min_chair_index if arrive_time == target_time
l_pq.push([a_top.last, min_chair_index])
else
unless c_pq.empty?
chair_index = c_pq.pop
return chair_index if arrive_time == target_time
l_pq.push([a_top.last, chair_index])
else
last_chair_index += 1
return last_chair_index if arrive_time == target_time
l_pq.push([a_top.last, last_chair_index])
end
l_pq.push(l_top)
end
end
end
end