updated tcr

1 files changed, 13 insertions, 0 deletions

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++;
+}