11/2 (목) 쿼리를 포함하기 위한 최소 인터벌 TIL

TIL | WIL

11/2 (목) 쿼리를 포함하기 위한 최소 인터벌 TIL

깊은바다거북 2023. 11. 2. 17:49

공부한 것

LeetCode #1851. Minimum Interval to Include Each Query

최소 힙을 사용하니 걸리는 시간이 대폭 줄어들었다. ‘최소값’이라는 키워드가 나왔을 때 최소 힙을 떠올렸어야 했는데.

해답 코드:

function minInterval3(intervals: number[][], queries: number[]): number[] {
	const sortedQueries = queries.map((q, i) => [q, i]).sort((a, b) => a[0] - b[0]);
	intervals.sort((a, b) => a[0] - b[0]);

	const heap = new MinHeap();
	const result = new Array(queries.length);

	let i = 0; 

	for (const [query, index] of sortedQueries) {
		while (i < intervals.length && intervals[i][0] <= query) {
			const [start, end] = intervals[i];
			heap.insert([end - start + 1, end]);
			i++;
		}

		while (heap.size && query > heap.min[1]) {
			heap.remove();
		}

		result[index] = heap.size ? heap.min[0] : -1;
	}
	
	return result;
}


class MinHeap {
	private heap: [number, number][] = [];

	get min() {
		return this.heap[0];
	}

	get size() {
		return this.heap.length;
	}

	insert(val: [number, number]) {
		this.heap.push(val);
		this.bubbleUp(this.size - 1);
	}

	remove() {
		if (!this.size) return;

		this.swap(0, this.size - 1);
		const min = this.heap.pop();
		this.bubbleDown(0);
		return min;
	}

	// 현재 index 자리의 노드를 min heap 규칙에 맞도록 끌어올린다.
	private bubbleUp(index: number) {
		// 지금 자리가 루트(root)에 도달하거나, 부모의 size값 이상이 될 때까지 반복 
		while (index > 0) {
			const parentIndex = Math.floor((index - 1) / 2);

			// 지금 자리의 size값이 부모 자리의 size값보다 작을 때만 자리 교체
			if (this.heap[index][0] < this.heap[parentIndex][0]) {
				this.swap(index, parentIndex);
				index = parentIndex;
			} else {
				break;
			}
		}
	}

	// 현재 index 자리의 노드를 min heap 규칙에 맞도록 끌어내린다.
	private bubbleDown(index: number) {
		// 지금 자리가 힙의 끝에 도달하거나, 두 자식의 size값 미만이 될 때까지 반복
		while (index < this.size) {
			const leftChildIndex = index * 2 + 1;
			const rightChildIndex = index * 2 + 2;
			let smallest = index;

			if (leftChildIndex < this.size && this.heap[leftChildIndex][0] < this.heap[smallest][0])
				smallest = leftChildIndex;
			
			if (rightChildIndex < this.size && this.heap[rightChildIndex][0] < this.heap[smallest][0])
				smallest = rightChildIndex;

			if (index === smallest) break;

			this.swap(index, smallest);
			index = smallest;
		}
	}

	private swap(i: number, j: number) {
		[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];
	}
}

Uploaded by N2T