java 解法, 执行用时: 26 ms, 内存消耗: 91.6 MB, 提交时间: 2023-10-08 17:47:04

class Solution {
    public int maxTwoEvents(int[][] events) {
        Arrays.sort(events,(a,b)->a[0]-b[0]);//按照开始时间排序
        int max[]=new int[events.length];//max[i]表示的是从i以后最大的活动价值
        max[events.length-1]=events[events.length-1][2];
        for(int i=events.length-2;i>=0;i--){max[i]=Math.max(max[i+1],events[i][2]);}
        int ans=0;
        for(int i=0;i<events.length;i++){
            if(events[i][1]<events[events.length-1][0]){ans=Math.max(ans,events[i][2]+max[nextMax(events,i)]);}
            else{ans=Math.max(ans,events[i][2]);}
        }
        return ans;
    }
    
    public int nextMax(int events[][],int j){
        //寻找j活动之后最大的那个时间戳处后可以继续参加的最早活动的index
        int l=j+1,r=events.length-1;
        while(l<r){
            int mid=(l+r)>>1;
            if(events[mid][0]<=events[j][1]){l=mid+1;}
            else{r=mid;}
        }
        return l;
    }
}

cpp 解法, 执行用时: 636 ms, 内存消耗: 134.6 MB, 提交时间: 2023-10-08 17:46:22

struct Event {
    // 时间戳
    int ts;
    // op = 0 表示左边界，op = 1 表示右边界
    int op;
    int val;
    Event(int _ts, int _op, int _val): ts(_ts), op(_op), val(_val) {}
    bool operator< (const Event& that) const {
        return tie(ts, op) < tie(that.ts, that.op);
    }
};

class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        vector<Event> evs;
        for (const auto& event: events) {
            evs.emplace_back(event[0], 0, event[2]);
            evs.emplace_back(event[1], 1, event[2]);
        }
        sort(evs.begin(), evs.end());
        
        int ans = 0, bestFirst = 0;
        for (const auto& [ts, op, val]: evs) {
            if (op == 0) {
                ans = max(ans, val + bestFirst);
            }
            else {
                bestFirst = max(bestFirst, val);
            }
        }
        return ans;
    }
};

python3 解法, 执行用时: 1184 ms, 内存消耗: 79.8 MB, 提交时间: 2023-10-08 17:45:35

class Event:
    def __init__(self, ts: int, op: int, val: int):
        self.ts = ts
        self.op = op
        self.val = val
    
    def __lt__(self, other: "Event") -> bool:
        return (self.ts, self.op) < (other.ts, other.op)


class Solution:
    def maxTwoEvents(self, events: List[List[int]]) -> int:
        evs = list()
        for event in events:
            evs.append(Event(event[0], 0, event[2]))
            evs.append(Event(event[1], 1, event[2]))
        evs.sort()

        ans = bestFirst = 0
        for ev in evs:
            if ev.op == 0:
                ans = max(ans, ev.val + bestFirst)
            else:
                bestFirst = max(bestFirst, ev.val)
        
        return ans

php 解法, 执行用时: 1048 ms, 内存消耗: 139.7 MB, 提交时间: 2023-10-08 17:44:41

class Solution {

    /**
     * @param Integer[][] $events
     * @return Integer
     */
    function maxTwoEvents($events) {
        $evs = [];
        foreach ($events as [$s, $e, $v]) {
            $evs[] = [$s, 0, $v];
            $evs[] = [$e, 1, $v];
        }
        sort($evs);
        $bestFirst = $ans = 0;
        foreach ($evs as [$_, $op, $v]) {
            if ($op) $bestFirst = max($bestFirst, $v);
            else $ans = max($ans, $bestFirst + $v);
        }
        return $ans;
    }
}

golang 解法, 执行用时: 256 ms, 内存消耗: 19.3 MB, 提交时间: 2023-10-08 17:43:54

func maxTwoEvents(events [][]int) (ans int) {
	sort.Slice(events, func(i, j int) bool { return events[i][0] < events[j][0] }) // 按开始时间排序
	h := hp{}
	maxVal := 0
	for _, e := range events {
		start, end, val := e[0], e[1], e[2]
		for len(h) > 0 && h[0].end < start { // 如果结束时间早于当前活动开始时间
			maxVal = max(maxVal, heap.Pop(&h).(pair).val) // 更新前面可以选择的活动的最大价值
		}
		ans = max(ans, maxVal+val) // 至多参加两个活动
		heap.Push(&h, pair{end, val})
	}
	return
}

// heap 模板
type pair struct{ end, val int }
type hp []pair
func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].end < h[j].end }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
func max(a, b int) int { if b > a { return b }; return a}