求指点优惠券最优匹配算法？

Question

问题描述

我这是个优惠券的模块

优惠券有3种：指定商品优惠券；供应商优惠券；全场通用优惠券；

每个订单只能使用一张优惠券

使用优先规则

1，金额最大并且符合条件优先使用

2，金额一样的话优先按 指定的商品 - 指定供应商 - 全场通用 从高至低优先级使用

现在假设 我在购物车同时结算2个不同供应商的商品（不同供应商会分订单）A 和 B ，现在我有2张符合条件的优惠券，一张指定A商品的优惠券 20元，一张全场通用券30元，按照之前的规则，会自动选择A商品使用全场优惠券，B就不能使用优惠券了。

但是如果A用20的优惠券，B也能用通用优惠券。我卡在这里了- -

求大佬指点迷津！！我是个小渣渣，我渴望进步！

Answer 1

说一下算法思路吧, 以下python伪代码
订单数组 A (A0, A1...An) n个， 优惠券数组 B (B0,B1...Bm), 其中B0 (金额、类型)，类型：A0~An或c0~ck指定供应商或M全场通用。

#用一个hashmap存下来类型数组, 并用排序
d = {}
for i in B:
    if i[1] in d:
        bisect.insort(d[i[1]], i[0]) #二分法有序插入金额
    else:
        d[i[1]] = [i[0]] # 金额数组
#时间复杂度O(mlogk) (k<=m)
#懒得用A的优惠券数组了，A也用hashmap，第一遍给所有的商品分配最高的商品优惠券
a = {} #key商品名，value优惠券价格
for i in A:
    if i in d:
        a[i] = d[i][0] #最高优惠券
        d[i].pop(0)
    else:
        a[i] = 0 #没有商品优惠券0
#时间复杂度O(n)
#第二遍分组从低到高给所有的商品分配最高的供应商优惠券
#供应商字典C (C0,...Ck) 其中C0的value 是(A0,..At)
for c in C:
    r = sorted([(a[i], i) for i in C[c]], lambda x: x[0]) # 根据价格排序，同组价格低的排最前面
    if not r:
        continue #没有这个组不用计算啦
    rindex = 0
    while d[c]: #还有供应商优惠券
        if d[c][0] <= r[rindex][0]:
            break #比商品优惠券低，不要算啦
        a[r[rindex][1]] = d[c][0] #低的商品优惠券不要啦，给高的供应商优惠券
        rindex += 1
        d[c].pop(0)
#时间复杂度O(k.tlogt)
#最后给全场优惠券啦
r = sorted([(a[i], i) for i in a], lambda x: x[0])# 根据价格排序，价格低的排最前面
rindex = 0
while d['M']: # 有全场通用券
    if d['M'][0] <= r[rindex][0]:
        break #全场通用券太低啦，不要算啦
    a[r[rindex][1]] = d['M'][0] #低的优惠券不要啦，给高的全场通用券
    rindex += 1
    d['M'].pop(0)
    
print(a) #最后的结果啦
#时间复杂度O(nlogn)

#总得时间复杂度取决于t、n、m的大小啦

Answer 2

首先你的规则都没定清楚：金额最大的券优先使用 还是 用途范围最窄优先使用？