segments.rb

#ruby 2.3.1
require 'rbtree' # gem install rbtree

input = [
  { start:1, end: 40, price: 500 },
  { start:10, end: 22, price: 1000 },
  { start:22, end: 33, price: 700 },
  { start:39, end: 42, price: 800 },
]

def calculate(input)#сложность O(n * log(n)) где n - размер входного массива
  priceEvents = []
  
  input.each do |data|#сложность O(n)
    priceEvents.push({time: data[:start], type: :start, price: data[:price]})
    priceEvents.push({time: data[:end], type: :end, price: data[:price]})
  end
  
  priceEvents.sort! do |l,r|#сложность O(n*log(n))
    if l[:time] != r[:time]
      l[:time] <=> r[:time] 
    else
      if l[:type] == r[:type]
        0
      else
        l[:type] == :end ? -1 : 1   
      end
    end
  end
  
  tree = RBTree.new
  tree.readjust {|l, r| r <=> l }

  result = []
  current = nil
  
  priceEvents.each do |event| #сложность O(n*log(n)) - 2n итераций,
    #каждая из которых не сложнее O(log(n))
    price = event[:price]
    time = event[:time]
    if current
      if event[:type] == :start
        tree[price] = (tree[price] || 0) + 1
        if current[:price] < price
          current[:end] = time
          result.push(current) if current[:end] != current[:start]
          current = {start: time, price: price}
        end
      else
        tree[price] -= 1
        if tree[price] == 0
          tree.delete price
          if current[:price] == price
            current[:end] = time
            result.push(current) if current[:end] != current[:start]
            if tree.first
              current = {start: time, price: tree.first.first}
            else
              current = nil
            end
          end
        end
      end
    else
      current = {start: time, price: price}
      tree[event[:price]] = 1
    end  
  end
  
  return result
end