ruby 中最小未占用椅子数的解决方案
The Number of the Smallest Unoccupied Chair solution in ruby
我正在学习ruby并开始练习leetcode的问题，昨天我有一个问题，从昨天开始我无法解决
我在 ruby 中努力做到了，但还做不到。
我试过了
def give_chair(a)
u = a.uniq
d = []
u.each do |i|
d << i if a.count(i) == 1
end
d
end
def smallest_chair(times, target_friend)
friend = times[target_friend]
sorted_arrival_times = times.sort
leave_time_chair = {}
chair = 0
chairs_array = []
uniq_chars_array = []
sorted_arrival_times.each do |i|
if leave_time_chair.keys.select { |k| i[0] > k }.empty?
leave_time_chair[i[1]] = chair
chair+=1
else
all_keys = leave_time_chair.keys.select { |k| k <= i[0] }
chairs_array = leave_time_chair.values
p chairs_array
if give_chair(chairs_array).empty?
leave_time_chair[i[1]] = chairs_array.sort.first
else
leave_time_chair[i[1]] = give_chair(chairs_array).sort.first
end
end
if i == friend
p leave_time_chair
return leave_time_chair[i[1]]
end
end
end
# a = [[33889,98676],[80071,89737],[44118,52565],[52992,84310],[78492,88209],[21695,67063],[84622,95452],[98048,98856],[98411,99433],[55333,56548],[65375,88566],[55011,62821],[48548,48656],[87396,94825],[55273,81868],[75629,91467]]
# b = 6
# p smallest_chair(a, b)
但某些测试用例失败了。
我无法为其创建算法。
问题=https://leetcode.com/problems/the-number-of-the-smallest-unoccupied-chair
我的做法：
首先我根据到达时间对时间数组进行排序。
然后我遍历每个数组元素
现在，如果到达时间大于所有之前的离开时间（我正在创建离开时间和给定椅子的键值对），那么我在 leave_time_chair （这是哈希），其中键是当前数组的离开时间，值是给它的椅子。
然后我增加椅子（椅子+=1）
否则我得到所有等于或小于当前到达时间的离开时间(all_keys = leave_time_chair.keys.select { |k| k <= i[0] })
那时候的椅子我都搞定了
现在我有所有这样的椅子 => [0, 0, 1, 2] 所以我写了一个函数 [ give_chair(a) ] 它给了我那些元素不再重复。像这样 => [1, 2] 然后我将最短的数字（椅子）分配给当前数组的离开时间。等等...
那如果我的当前数组等于我return的朋友的椅子呢。通过从哈希中提取它 (leave_time_chair) return leave_time_chair[i[1]]
我天真的解决方案（尚未优化），基本上我的想法是我将输入数组平面映射到一个数组中，每个元素都是一对 [time arrive/leave, friend index]，然后我将根据时间对该数组进行排序（不在乎到达或离开），如果两对时间相同，那么我将比较 fiend 索引的到达时间。最后，我循环遍历排序数组并评估 minimum free chair index 每一步，每当我遇到 targetFriend 我 return 即 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
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
smallest_chair 优先级队列（注意我发现使用 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
我正在学习ruby并开始练习leetcode的问题，昨天我有一个问题，从昨天开始我无法解决
我在 ruby 中努力做到了，但还做不到。
我试过了
def give_chair(a)
u = a.uniq
d = []
u.each do |i|
d << i if a.count(i) == 1
end
d
end
def smallest_chair(times, target_friend)
friend = times[target_friend]
sorted_arrival_times = times.sort
leave_time_chair = {}
chair = 0
chairs_array = []
uniq_chars_array = []
sorted_arrival_times.each do |i|
if leave_time_chair.keys.select { |k| i[0] > k }.empty?
leave_time_chair[i[1]] = chair
chair+=1
else
all_keys = leave_time_chair.keys.select { |k| k <= i[0] }
chairs_array = leave_time_chair.values
p chairs_array
if give_chair(chairs_array).empty?
leave_time_chair[i[1]] = chairs_array.sort.first
else
leave_time_chair[i[1]] = give_chair(chairs_array).sort.first
end
end
if i == friend
p leave_time_chair
return leave_time_chair[i[1]]
end
end
end
# a = [[33889,98676],[80071,89737],[44118,52565],[52992,84310],[78492,88209],[21695,67063],[84622,95452],[98048,98856],[98411,99433],[55333,56548],[65375,88566],[55011,62821],[48548,48656],[87396,94825],[55273,81868],[75629,91467]]
# b = 6
# p smallest_chair(a, b)
但某些测试用例失败了。
我无法为其创建算法。
问题=https://leetcode.com/problems/the-number-of-the-smallest-unoccupied-chair
我的做法：
首先我根据到达时间对时间数组进行排序。
然后我遍历每个数组元素
现在，如果到达时间大于所有之前的离开时间（我正在创建离开时间和给定椅子的键值对），那么我在 leave_time_chair （这是哈希），其中键是当前数组的离开时间，值是给它的椅子。
然后我增加椅子（椅子+=1）
否则我得到所有等于或小于当前到达时间的离开时间(
all_keys = leave_time_chair.keys.select { |k| k <= i[0] })那时候的椅子我都搞定了
现在我有所有这样的椅子 => [0, 0, 1, 2] 所以我写了一个函数 [ give_chair(a) ] 它给了我那些元素不再重复。像这样 => [1, 2] 然后我将最短的数字（椅子）分配给当前数组的离开时间。等等...
那如果我的当前数组等于我return的朋友的椅子呢。通过从哈希中提取它 (leave_time_chair) return leave_time_chair[i[1]]
我天真的解决方案（尚未优化），基本上我的想法是我将输入数组平面映射到一个数组中，每个元素都是一对 [time arrive/leave, friend index]，然后我将根据时间对该数组进行排序（不在乎到达或离开），如果两对时间相同，那么我将比较 fiend 索引的到达时间。最后，我循环遍历排序数组并评估 minimum free chair index 每一步，每当我遇到 targetFriend 我 return 即 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
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
smallest_chair 优先级队列（注意我发现使用 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