0

条件：必须使用基于 Web 的解决方案（HTML/CSS），必须使用 Ruby on Rails，不使用数据库。

想象一下，我们有一个工作列表，每个工作都由一个字符表示。因为某些工作必须在其他工作之前完成，所以一项工作可能依赖于另一项工作。例如，a 可能依赖于 b，这意味着最终的作业序列应将 b 放在 a 之前。如果 a 没有依赖关系，则 a 在最终序列中的位置无关紧要。这些作业将使用一个简单的文本框输入（以及如何存储多个变量）

给定以下工作结构：

  • 一个=>
  • 乙 =>
  • c =>

结果应该是包含所有三个作业 abc 的序列，顺序不重要。

给定以下工作结构：

  • 一个=>
  • b => c
  • c => f
  • d => 一个
  • e => b
  • f =>

结果应该是一个包含所有六个作业 abcdef 的序列，其中 f 位于 c 之前，c 位于 b 之前，b 位于 e 之前，a 位于 d 之前。

给定以下工作结构：

  • 一个=>
  • b => c
  • c => f
  • d => 一个
  • e =>
  • f => b

结果应该是一个错误，指出作业不能有循环依赖。

4

1 回答 1

0

这应该有效：

module JobDependenciesResolver    

  def self.organize(dependencies)
    unresolved_dependencies = dependencies.dup
    sorted_jobs = []

    until unresolved_dependencies.empty? do
      doable_jobs = get_doable_jobs unresolved_dependencies, sorted_jobs
      raise Exception.new("Not able to resolve dependencies") if doable_jobs.empty?
      sorted_jobs += doable_jobs
      unresolved_dependencies.delete_if {|key,value| sorted_jobs.include? key}
    end

    sorted_jobs
  end

  private

  def self.get_doable_jobs(dependencies, job_array)
    dependencies.select {|job, dependency| ([*dependency]-job_array).empty? }.keys        
  end
end
于 2013-08-09T15:59:48.033 回答