732. My Calendar III

leetcode hard

#csharp#hard#hash-table#leetcode#math#sort

Task

k-бронирование происходит, когда k событий имеют некоторое непустое пересечение (т.е, дано некоторое время, общее для всех k событий). Даны некоторые события [startTime, endTime), после каждого данного события верните целое число k, представляющее максимальное k-бронирование между всеми предыдущими событиями. Реализация класса MyCalendarThree: MyCalendarThree() Инициализирует объект. int book(int startTime, int endTime) Возвращает целое число k, представляющее наибольшее целое число, при котором в календаре существует k-бронирование.

Пример:

Input

["MyCalendarThree", "book", "book", "book", "book", "book", "book"]

[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

Output

[null, 1, 1, 2, 3, 3, 3]

C# solution

matched/original

using System;
using System.Collections.Generic;
public class MyCalendarThree {
    private SortedDictionary<int, int> events;
    public MyCalendarThree() {
        events = new SortedDictionary<int, int>();
    }
    public int Book(int startTime, int endTime) {
        if (!events.ContainsKey(startTime)) {
            events[startTime] = 0;
        }
        if (!events.ContainsKey(endTime)) {
            events[endTime] = 0;
        }
        events[startTime]++;
        events[endTime]--;
        
        int active = 0;
        int maxActive = 0;
        foreach (var count in events.Values) {
            active += count;
            maxActive = Math.Max(maxActive, active);
        }
        
        return maxActive;
    }
}

C++ solution

auto-draft, review before submit

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

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class MyCalendarThree {
    private SortedDictionary<int, int> events;
    public MyCalendarThree() {
        events = new SortedDictionary<int, int>();
    }
    public int Book(int startTime, int endTime) {
        if (!events.count(startTime)) {
            events[startTime] = 0;
        }
        if (!events.count(endTime)) {
            events[endTime] = 0;
        }
        events[startTime]++;
        events[endTime]--;
        
        int active = 0;
        int maxActive = 0;
        foreach (var count in events.Values) {
            active += count;
            maxActive = max(maxActive, active);
        }
        
        return maxActive;
    }
}

Java solution

matched/original

import java.util.Map;
import java.util.TreeMap;

public class MyCalendarThree {
    private TreeMap<Integer, Integer> events;

    public MyCalendarThree() {
        events = new TreeMap<>();
    }

    public int book(int startTime, int endTime) {
        events.put(startTime, events.getOrDefault(startTime, 0) + 1);
        events.put(endTime, events.getOrDefault(endTime, 0) - 1);
        
        int active = 0;
        int maxActive = 0;
        for (Map.Entry<Integer, Integer> entry : events.entrySet()) {
            active += entry.getValue();
            maxActive = Math.max(maxActive, active);
        }
        
        return maxActive;
    }
}

JavaScript solution

matched/original

class MyCalendarThree {
    constructor() {
        this.events = {};
    }

    book(startTime, endTime) {
        this.events[startTime] = (this.events[startTime] || 0) + 1;
        this.events[endTime] = (this.events[endTime] || 0) - 1;
        
        let active = 0;
        let maxActive = 0;
        const times = Object.keys(this.events).map(Number).sort((a, b) => a - b);
        
        for (let time of times) {
            active += this.events[time];
            maxActive = Math.max(maxActive, active);
        }
        
        return maxActive;
    }
}

Python solution

matched/original

from collections import defaultdict

class MyCalendarThree:
    def __init__(self):
        self.start_times = defaultdict(int)
        self.end_times = defaultdict(int)

    def book(self, startTime, endTime):
        self.start_times[startTime] += 1
        self.end_times[endTime] += 1
        
        active = 0
        max_active = 0
        for time in sorted(self.start_times.keys()):
            active += self.start_times[time]
            if time in self.end_times:
                active -= self.end_times[time]
            max_active = max(max_active, active)
        
        return max_active

Go solution

matched/original

package main

import "sort"

type MyCalendarThree struct {
    events map[int]int
}

func Constructor() MyCalendarThree {
    return MyCalendarThree{events: make(map[int]int)}
}

func (this *MyCalendarThree) Book(startTime int, endTime int) int {
    this.events[startTime]++
    this.events[endTime]--
    
    times := make([]int, 0, len(this.events))
    for time := range this.events {
        times = append(times, time)
    }
    sort.Ints(times)
    
    active := 0
    maxActive := 0
    for _, time := range times {
        active += this.events[time]
        if active > maxActive {
            maxActive = active
        }
    }
    
    return maxActive
}

Explanation

Algorithm

Создайте два словаря для хранения изменений времени бронирования: один для начала событий, другой для конца событий.

Для каждого нового события обновите словари начала и конца событий.

Поддерживайте текущее количество активных бронирований и обновляйте максимальное количество активных бронирований по мере добавления новых событий.

😎