From 5ab8a5088b729a9953b8dff1b2a985dc8fb2098b Mon Sep 17 00:00:00 2001
From: mzuenni <michi.zuendorf@gmail.com>
Date: Mon, 27 Jun 2022 17:19:28 +0200
Subject: updated tcr

---
 datastructures/firstUnused.cpp | 13 +++++++++++++
 1 file changed, 13 insertions(+)
 create mode 100644 datastructures/firstUnused.cpp

(limited to 'datastructures/firstUnused.cpp')

diff --git a/datastructures/firstUnused.cpp b/datastructures/firstUnused.cpp
new file mode 100644
index 0000000..16b0c21
--- /dev/null
+++ b/datastructures/firstUnused.cpp
@@ -0,0 +1,13 @@
+// Erste natürliche Zahl nicht im set used.
+set<int> used;
+int unusedCounter = 1;
+
+int get_first_unused() { // Laufzeit: O(log n) amortisiert.
+	auto it = used.lower_bound(unusedCounter);
+	while (it != used.end() && *it == unusedCounter) {
+		it++;
+		unusedCounter++;
+	}
+	used.insert(unusedCounter);
+	return unusedCounter++;
+}
-- 
cgit v1.2.3