Given an array of meeting time intervals consisting of start and end timesContinue reading “[Leetcode]253. Meeting Rooms II”`[[s1,e1],[s2,e2],...]`

(s_{i}< e_{i}), find the minimum number of conference rooms required.Example 1:Input:`[[0, 30],[5, 10],[15, 20]]`

Output:2

## [Leetcode problems]1488. Avoid Flood in The City

Your country has an infinite number of lakes. Initially, all the lakes are empty, but when it rains over theContinue reading “[Leetcode problems]1488. Avoid Flood in The City”`nth`

lake, the`nth`

lake becomes full of water. If it rains over a lake which isfull of water, there will be aflood. Your goal is to avoid the flood in any lake. Given an integer array`rains`

where:`rains[i] > 0`

means there will be rains over the`rains[i]`

lake.`rains[i] == 0`

means there are no rains this day and you can chooseone lakethis day anddry it. Returnan arraywhere:`ans`

`ans.length == rains.length`

`ans[i] == -1`

if`rains[i] > 0`

.`ans[i]`

is the lake you choose to dry in the`ith`

day if`rains[i] == 0`

. If there are multiple valid answers returnanyof them. If it is impossible to avoid flood returnan empty array. Notice that if you chose to dry a full lake, it becomes empty, but if you chose to dry an empty lake, nothing changes. (see example 4)Example 1:Input:rains = [1,2,3,4]Output:[-1,-1,-1,-1]Example 2:Input:rains = [1,2,0,0,2,1]Output:[-1,-1,2,1,-1,-1]

## Top K problem – Sort, Heap, and Quickselect

Top K problem refers to those asking to find the Kth largest/smallest element or the top K largest/smallest items from an unsorted array. Sorting first and returning the Kth item definitely works, yet it yields O(n^2) or O(nlogn) time complexity. With heap or quickselect, O(n) is achievable.

Continue reading “Top K problem – Sort, Heap, and Quickselect”