[JavaScript] 2054. Two Best Non-Overlapping Events
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\n\nPrevious approach\n\n\n1 only 2 event values needed\n2 their sum must b
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n\nPrevious approach\n\n```\n1 only 2 event values needed\n2 their sum must be max\n3 the events must be non-overlapping ( seperate )\n\nsort events by end times\nmaxsum = 0\nfor each event (start, end, value)\n    find an event that is before start\n        till that event find max of all values - value2\n    sum = value + value2\n    if (sum > maxsum)\n        maxsum = sum\nreturn maxsum\n\nfind an event\n    this can be linear ( as given below ) - O(N) - slow\n    this can be done via binary search - O(log N) - 10X faster\n\n```\n\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n\n**New code** ( since new test cases were added )\n\n---\n\n```\nvar maxTwoEvents = function (events) {\n\tevents.sort((a, b) => a[0] - b[0]); // sort by event start times\n\tconst pqEventEndVal = new PriorityQueue({ compare: (a, b) => a[0] - b[0] });\n\tlet maxPreviousEventVal = 0;\n\tlet maxTwoNonOverlappingEventsValSum = 0;\n\tfor (const [s, e, currentVal] of events) {\n\t\t// remove  previous events  before current start,  from pq, if exists\n\t\twhile (pqEventEndVal.size() && pqEventEndVal.front()[0] < s) {\n\t\t\tconst [prevEventTime, prevEventValue] = pqEventEndVal.dequeue();\n\t\t\tmaxPreviousEventVal = Math.max(maxPreviousEventVal, prevEventValue);\n\t\t}\n\t\tmaxTwoNonOverlappingEventsValSum = //\n\t\t\tMath.max(maxTwoNonOverlappingEventsValSum, maxPreviousEventVal + currentVal);\n\t\tpqEventEndVal.enqueue([e, currentVal]); // for future\n\t}\n\treturn Math.max(maxTwoNonOverlappingEventsValSum, maxPreviousEventVal); // Return the best possible sum\n};\n```\n\n---\n
['JavaScript']