关于 拼多多笔试题-简单易懂的秒杀服务

作者：ChenBuJiu
链接：https://www.nowcoder.com/discuss/37061?type=0&order=0&pos=11&page=0
来源：牛客网

实现一个简易的秒杀服务，有3个接口：

1. 添加一个秒杀活动 addActivity(int startTime, int endTime, int goodsId, int limitQuantity)

参数说明：

    * 时间区间为左闭右开：[startTime, endTime) 。数据保证 startTime < endTime，startTime 大于当前时间戳
    * goodsId 一定为存在的商品id。每个goodsId至多添加一次秒杀活动。
    * limitQuantity > 0 

返回值有以下两种情况：

    * 添加成功，返回秒杀活动ID (从0开始自增)
    * 秒杀商品数量大于商品库存，添加失败，返回-1

2. 购买秒杀商品 buyGoods(int activityId, int quantity)

参数说明：

    * activityId 一定是请求时存在的活动id
    * quantity > 0 

返回值有以下三种情况：

    * 购买成功，减少库存，返回0
    * 购买数量大于秒杀商品剩余数量，购买失败，返回-1
    * 秒杀未开始或已结束，购买失败，返回-1

3. 获取秒杀活动列表 getActivityList() 获取当前时刻的秒杀活动列表

秒杀列表排序方式：进行中(未售罄) > 进行中(售罄) > 未开始 

    * 对于「进行中(未售罄)」：依次按商品人气值从高到低、商品ID从小到大排序 
    * 对于「进行中(已售罄)」：依次按最后卖出时间从晚到早、商品人气值从高到低、商品ID从小到大排序 
    * 对于「未开始」：依次按开始时间从早到晚、商品人气值从高到低、商品ID从小到大排序
    * 对于已结束的秒杀，不返回。 

返回秒杀活动id列表

商品拥有以下属性：

* 商品ID，32位非负整数 
* 人气值，32位非负整数 
* 库存，32位非负整数

现给出一串请求，每个请求的格式为：时间戳 函数名 参数。请对每个请求都输出其返回结果 (请求已经按照时间先后顺序排序过) 。

数据范围：

* 商品数量 N <= 10,000
* 请求数量 M <= 10,000
* add 数量 A <= 1,000
* buy 数量 B <= 10,000 
* list 数量 L <= 100

输入描述:

第一行是两个整数 N 和 M ，分别表示商品数量和请求数量。
接下来有 N 行，每行表示一个商品，具体格式为：3个整数(被空格分隔)分别表示商品ID，人气值，库存
接下来有 M 行，每行表示一个请求，请求已经按时间戳从小到大排序。
具体格式为：时间戳 请求类型 请求参数...
  * 时间戳：正整数
  * 请求类型，共三种："add", "buy" 和 "list"
  * 请求参数：按题目描述中的顺序，参数之间空格分隔

输出描述:

对每个请求，输出其返回值，一个请求的输出占一行：
  * add：成功输出id，失败输出-1
  * buy：成功输出0，失败输出-1
  * list：输出活动id列表，按要求的顺序，相邻数字之间用一个空格分隔。若列表为空，则输出空行。

示例1

输入

6 13
1001 1 10
1002 1 10
1003 2 10
1004 2 10
1005 2 10
1006 3 10
1 add 2 20 1001 10
2 buy 0 1
3 buy 0 10
4 add 5 6 1002 2
5 list
6 buy 1 1
7 add 10 20 1003 11
8 add 10 20 1003 8
9 add 10 20 1004 3
10 add 11 20 1005 5
11 add 20 30 1006 1
12 buy 3 3
13 list

输出

0
0
-1
1
0 1
-1
-1
2
3
4
5
0
2 4 0 3 5

下面是我的python 解法，由于题目复杂，当时一下没A出来，后来补全了下

s = raw_input().split(" ")
n, m = int(s[0]), int(s[1])


class Good(object):
    def __init__(self, good_id, pop, num):
        self.good_id = good_id
        self.pop = pop
        self.num = num


class Activity(object):
    index = 0

    def __init__(self, start_time, end_time, good_object, limit):
        self.start_time = start_time
        self.end_time = end_time
        self.good_object = good_object
        self.limit = limit
        self.last_sell = 0
        self.activity_id = Activity.index
        Activity.index += 1

goods_dict = dict()
for i in xrange(n):
    s = raw_input().split(" ")
    good_id = int(s[0])
    pop = int(s[1])
    num = int(s[2])
    goods_dict[good_id] = Good(good_id, pop, num)

unstart_dict = dict()
running_dict = dict()
empty_dict = dict()

def update(moment):

    del_list = []
    for key, item in empty_dict.iteritems():
        if item.end_time <= moment:
            del_list.append(key)

    for key in del_list:
        del empty_dict[key]

    del_list = []
    for key, item in running_dict.iteritems():
        if item.end_time <= moment:
            del_list.append(key)
            continue
        if item.limit <= 0:
            empty_dict[key] = item
            del_list.append(key)
    for key in del_list:
        del running_dict[key]

    del_list = []
    for key, item in unstart_dict.iteritems():
        if item.start_time <= moment:
            running_dict[key] = item
            del_list.append(key)
    for key in del_list:
        del unstart_dict[key]

    # print "unstart_dict", str(unstart_dict)
    # print "running_dict", str(running_dict)
    # print "empty_dict", str(empty_dict)

for i in xrange(1, m + 1):
    update(i)
    s = raw_input().split(" ")
    op = s[1]
    if op == "add":
        start_time = int(s[2])
        end_time = int(s[3])
        good_id = int(s[4])
        limit = int(s[5])
        if limit > goods_dict[good_id].num:
            print -1
            continue
        activity = Activity(start_time, end_time, goods_dict[good_id], limit)
        unstart_dict[activity.activity_id] = activity
        print activity.activity_id
    elif op == "buy":
        activity_id = int(s[2])
        quantity = int(s[3])
        if activity_id in running_dict and running_dict[activity_id].limit >= quantity:
            running_dict[activity_id].limit -= quantity
            running_dict[activity_id].good_object.num -= quantity
            running_dict[activity_id].last_sell = i
            print 0
        else:
            print -1
    elif op == "list":

        def cmp_unstart(x, y):
            if x.start_time == y.start_time:
                if x.good_object.pop == y.good_object.pop:
                    return x.good_object.good_id - y.good_object.good_id
                return y.good_object.pop - x.good_object.pop
            return x.start_time - y.start_time

        def cmp_running(x, y):
            if x.good_object.pop == y.good_object.pop:
                return x.good_object.good_id - y.good_object.good_id
            return y.good_object.pop - x.good_object.pop

        def cmp_empty(x, y):
            if x.last_sell == y.last_sell:
                if x.good_object.pop == y.good_object.pop:
                    return x.good_object.good_id - y.good_object.good_id
                return y.good_object.pop - x.good_object.pop
            return y.last_sell - x.last_sell


        unstart_list = sorted(unstart_dict.values(), cmp=cmp_unstart)
        running_list = sorted(running_dict.values(), cmp=cmp_running)
        empty_list = sorted(empty_dict.values(), cmp=cmp_empty)

        for activity in running_list:
            print activity.activity_id,
        for activity in empty_list:
            print activity.activity_id,
        for activity in unstart_list:
            print activity.activity_id,
        print ""

大家看下有没有更好的方法~