Solution based on C++ set -- memory limit exceeded?


  • 2
    S

    My solution uses a C++ set, as shown below. To do so, I use a custom SRInterval class. Two SRIntervals compare equal if they overlap. This makes it easy to find existing intervals that need to be merged.

    This solution received a "memory limit exceeded" verdict, and I cannot understand why. Any hints?

    struct SRInterval {
        const int begin;
        const int end;
        SRInterval(int begin, int end) : begin(begin), end(end) {}
        bool operator<(const SRInterval &other) const {
            return end <= other.begin;
        }
    };
    
    class SummaryRanges {
        set<SRInterval> intervals;
    
    public:
        void addNum(int val) {
            int b = val;
            int e = val + 1;
    
            auto left = intervals.find(SRInterval(val - 1, val));
            if (left != intervals.end()) {
                b = left->begin;
                intervals.erase(*left);
            }
            auto right = intervals.find(SRInterval(val, val + 2));
            if (right != intervals.end()) {
                e = right->end;
                intervals.erase(*right);
            }
    
            SRInterval sri(b, e);
            assert(intervals.count(sri) == 0 && "sri already in intervals?");
            intervals.insert(sri);
        }
        
        vector<Interval> getIntervals() {
            vector<Interval> result;
            result.reserve(intervals.size());
            for (auto &sri : intervals) {
                result.emplace_back(sri.begin, sri.end - 1);
            }
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.