Revision of dem.cpp

1 file changed, 34 insertions

dem.cpp(file created)

		@@ -0,0 +1,34 @@
1	+	int N = segments.size();
2	+
3	+
4	+	vector<vector<int>> sortedSegments = segments;
5	+	sort(sortedSegments.begin(), sortedSegments.end(), [](const vector<int> &a, const vector<int> &b) {
6	+	return a[1] < b[1];
7	+	});
8	+
9	+
10	+	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
11	+	int min_cost = numeric_limits<int>::max();
12	+
13	+	for (const auto &segment : sortedSegments) {
14	+	int L = segment[0];
15	+	int R = segment[1];
16	+	int cost = segment[2];
17	+
18	+
19	+	while (!minHeap.empty() && minHeap.top().first >= L) {
20	+	minHeap.pop();
21	+	}
22	+
23	+
24	+	if (!minHeap.empty()) {
25	+	int pairing_cost = minHeap.top().second * cost;
26	+	min_cost = min(min_cost, pairing_cost);
27	+	}
28	+
29	+
30	+	minHeap.push({R, cost});
31	+	}
32	+
33	+	return (min_cost != numeric_limits<int>::max()) ? min_cost : -1;
34	+	}

Newer Older