Affirm

01Redeemable Promotion Offers

You are given promotion offer definitions and user redemption events. Each offer string has the format offerId,startDate,endDate,maxRedeemsPerUser. Each event string has the format userId,date,action,offerId, where action is either redeem or unredeem. For every user that appears in the event log, determine which offers they can still redeem on cutoffDate. An offer is redeemable if the cutoff date is within the offer's date range and the user's net redeemed count for that offer is less than maxRedeemsPerUser. Return one line per user in ascending user id order as userId:offerA,offerB, with offer ids sorted ascending. If no user can redeem any offer, return ["None"].

Constraints

Dates use ISO YYYY-MM-DD strings and can be compared lexicographically.

Example 1

Input:

offers = ["O1,2015-01-01,2015-12-31,2","O2,2015-06-01,2016-01-31,1"]
events = ["u1,2015-07-01,redeem,O1","u1,2015-07-02,redeem,O1","u1,2015-08-01,redeem,O2","u1,2015-09-01,unredeem,O1","u2,2015-08-01,redeem,O1"]
cutoffDate = "2015-12-31"

Output:

["u1:O1","u2:O1,O2"]

Explanation: User u1 has one remaining redemption for O1 but none for O2. User u2 can redeem both active offers.

Example 2

Input:

offers = ["A,2015-01-01,2015-01-31,1"]
events = ["u1,2015-01-02,redeem,A"]
cutoffDate = "2015-12-31"

Output:

["None"]

Explanation: The only offer has expired before the cutoff date.

解法

用哈希表统计 (userId, offerId) -> net redeem count，redeem 计 +1，unredeem 计 −1。按 userId 升序遍历，对每个用户按 offerId 升序枚举所有 offer：若 cutoffDate 在 [startDate, endDate] 内且净计数 < maxRedeemsPerUser，则该 offer 仍可兑换。设 N=events、M=offers、U=users，时间 O(N + U·M log M)，空间 O(N)。

from collections import defaultdict
from typing import List

def redeemable_offers(offers: List[str], events: List[str], cutoff_date: str) -> List[str]:
    # offer_id -> (start, end, max_per_user)
    offer_info = {}
    for o in offers:
        oid, start, end, max_red = o.split(",")
        offer_info[oid] = (start, end, int(max_red))

    # (user, offer) -> net redeem count
    counts: dict = defaultdict(int)
    users: set = set()
    for e in events:
        uid, _date, action, oid = e.split(",")
        users.add(uid)
        counts[(uid, oid)] += 1 if action == "redeem" else -1

    result = []
    for uid in sorted(users):
        eligible = []
        for oid in sorted(offer_info):
            start, end, cap = offer_info[oid]
            if start <= cutoff_date <= end and counts[(uid, oid)] < cap:
                eligible.append(oid)
        if eligible:
            result.append(f"{uid}:{','.join(eligible)}")
    return result if result else ["None"]

import java.util.*;

class Solution {
    public List<String> redeemableOffers(List<String> offers, List<String> events, String cutoffDate) {
        Map<String, String[]> offerInfo = new TreeMap<>();
        for (String o : offers) {
            String[] p = o.split(",");
            offerInfo.put(p[0], new String[]{p[1], p[2], p[3]});
        }

        Map<String, Integer> counts = new HashMap<>();
        TreeSet<String> users = new TreeSet<>();
        for (String e : events) {
            String[] p = e.split(",");
            users.add(p[0]);
            String key = p[0] + "|" + p[3];
            int delta = "redeem".equals(p[2]) ? 1 : -1;
            counts.merge(key, delta, Integer::sum);
        }

        List<String> out = new ArrayList<>();
        for (String uid : users) {
            List<String> eligible = new ArrayList<>();
            for (Map.Entry<String, String[]> e : offerInfo.entrySet()) {
                String oid = e.getKey();
                String[] v = e.getValue();
                int cap = Integer.parseInt(v[2]);
                int c = counts.getOrDefault(uid + "|" + oid, 0);
                if (v[0].compareTo(cutoffDate) <= 0 && cutoffDate.compareTo(v[1]) <= 0 && c < cap) {
                    eligible.add(oid);
                }
            }
            if (!eligible.isEmpty()) out.add(uid + ":" + String.join(",", eligible));
        }
        return out.isEmpty() ? List.of("None") : out;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<string> redeemableOffers(vector<string>& offers, vector<string>& events, string cutoffDate) {
        auto split = [](const string& s) {
            vector<string> out; string cur;
            for (char c : s) { if (c == ',') { out.push_back(cur); cur.clear(); } else cur += c; }
            out.push_back(cur); return out;
        };
        map<string, tuple<string,string,int>> info;
        for (auto& o : offers) {
            auto p = split(o);
            info[p[0]] = {p[1], p[2], stoi(p[3])};
        }
        unordered_map<string,int> counts;
        set<string> users;
        for (auto& e : events) {
            auto p = split(e);
            users.insert(p[0]);
            counts[p[0] + "|" + p[3]] += (p[2] == "redeem") ? 1 : -1;
        }
        vector<string> out;
        for (auto& uid : users) {
            string line;
            for (auto& [oid, t] : info) {
                auto& [s, e, cap] = t;
                int c = counts[uid + "|" + oid];
                if (s <= cutoffDate && cutoffDate <= e && c < cap) {
                    if (!line.empty()) line += ",";
                    line += oid;
                }
            }
            if (!line.empty()) out.push_back(uid + ":" + line);
        }
        return out.empty() ? vector<string>{"None"} : out;
    }
};