首页 > 试题广场 >

酒店价格

[编程题]酒店价格

热度指数：15399 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

酒店房间的价格录入是通过时间段来录入的，比如10月1日至10月7日800元，10月8日至10月20日500元，请实现以下函数int[][] merge(int[][] dateRangePrices)，输入是某个酒店多个日期段的价格，每个日期段（终止日期大于等于起始日期）和对应的价格使用长度为3的数组来表示，比如[0, 19, 300], [10, 40, 250]分别表示从某天开始第1天到第20天价格都是300，第11天到第41天价格都是250，这些日期端有可能重复，重复的日期的价格以后面的为准，请以以下规则合并并输出合并结果：
1.相邻两天的价格如果相同，那么这两个日期段应该合并
2.合并的结果应该以起始日期从小到大排序

输入描述:

输入数据包括多行，如样例输入所示。

输出描述:

输出数据为一行，如样例输出所示

示例1

输入

1 1 100
2 3 100
4 5 110

输出

[1, 3, 100],[4, 5, 110]

算法知识视频讲解

Python

ql123

"""
借鉴@老子是帮主
直接用一个数组存储每天的价格，这样做的好处就是即使前后数据不一致，后面
的会直接覆盖前面的完成价格更新，缺点就是需要一个数组来记录每天的价格，空间复杂
度较高，对于这个实际问题而言，不会出现特别多的天数，所以不必考虑大数问题，当然

也所幸内存够用。特别需要注意输出格式要满足题目要求。

注意：输出那里有空格
"""
if __name__ == '__main__':
   data = []
   while True:
       try:
           data.append(list(map(int,input().split())))
       except:
           break

   dp = [0]*10000
   min,max = data[0][0],data[0][1]
   for i in range(len(data)):
       for j in range(data[i][0],data[i][1]+1):
           dp[j] = data[i][2]
       if min > data[i][0]:
           min = data[i][0]
       if max < data[i][1]:
           max = data[i][1]
   #print(min,max)
   res = ''
   res += '['+str(min)+', '
   for i in range(min+1,max+1):
       if dp[i] != dp[i-1]:
           if dp[i-1] != 0:
               res += str(i-1)+', '+str(dp[i-1])+']'
           if i<max and dp[i] !=0:
               res += ','+'['+str(i)+', '
   res += str(max)+', '+str(dp[max])+']'
   print(res)

发表于 2018-08-20 20:27:21 回复(0)

Python

yufeifly

给一个python的解法：

import sys
hotel = {}
st, ed = sys.maxsize, -1 while True:  try:
        start,end,price=list(map(int,input().split()))
        st,ed = min(st, start),max(ed, end)  for i in range(start, end+1):
            hotel[i] = price  except:  break  cur_st,cur_ed = st, st
cur_mo = hotel[st]
ans = [] for key in hotel:  if hotel[key] != hotel[cur_st]:
        ans.append(list([cur_st, cur_ed, hotel[cur_st]]))
        cur_st,cur_ed = key, key  else:
        cur_ed = key  if key == ed:
            ans.append(list([cur_st, cur_ed, hotel[cur_st]])) print(','.join(str(i) for i in ans))

编辑于 2018-07-11 15:42:05 回复(1)

Python

离疏

#时间超时，只过了10%
hotel,i=[],0
while True:
    try:
        start,end,price=list(map(int,input().split()))
        hotel.append([start,end,price])
    except:
        break
sorted(hotel, key=lambda x:x[0])
while i<=len(hotel)-2:
    if hotel[i+1][2]==hotel[i][2]:#价格相等
        if hotel[i][1]>=hotel[i+1][0]-1:#前一段的end日期不小于后一段start日期-1，及两段日期相邻，则合并为一段
            hotel[i]=[hotel[i][0],hotel[i+1][1],hotel[i][2]]
            hotel.pop(i+1)
        else:
            i+=1
    else:#价格不等
        if hotel[i][1]>=hotel[i+1][0]:#前一段的end日期大于等于后一段的start日期，即有重合部分，则被覆盖至后一段start日期-1
            hotel[i]=[hotel[i][0],hotel[i+1][1]-1,hotel[i][2]]
        else:
            i+=1
print(','.join(str(x) for x in hotel))

发表于 2018-07-06 12:03:59 回复(2)

Python

新鲜菜鸡🐔

暴力也能过！
import sys
list_x = []
for line in sys.stdin.readlines():
    temp = [int(x) for x in line.split()]
    gg = []
    for i in range(len(list_x)):
        if temp[0]>list_x[i][0] and list_x[i][1]<=temp[1] and temp[0]<=list_x[i][1]:
            list_x[i][1] = temp[0]-1
            gg.append(list_x[i])
        elif temp[1]<list_x[i][1] and temp[0]>list_x[i][0]:
            gg.append([temp[1] + 1, list_x[i][1], list_x[i][2]])
            list_x[i][1] = temp[0]-1
            gg.append(list_x[i])
        elif temp[1]<list_x[i][1] and temp[1]>=list_x[i][0] and temp[0]<=list_x[i][0]:
            list_x[i][0] = temp[1] + 1
            gg.append(list_x[i])
        elif temp[0]<=list_x[i][0] and temp[1]>=list_x[i][1]:
            pass
        else:
            gg.append(list_x[i])
    gg.append(temp)
    list_x = gg

list_x = sorted(list_x,key=lambda x:x[0])
ans = []
start,end,value = list_x[0]

for i in range(1,len(list_x)):
    if list_x[i][0]==end+1 and list_x[i][2]==value:
        end = list_x[i][1]
    else:
        ans.append([start,end,value])
        start,end,value = list_x[i]
ans.append([start,end,value])
print(str(ans)[1:-1].replace(', [',',['))

发表于 2018-05-30 20:18:24 回复(0)