Added new solutions

Мето Трајковски · Мето Трајковски · commit b5e5bce862a0 · 2019-12-09T16:42:08.000+01:00
diff --git a/Lists/find_all_intervals.py b/Lists/find_all_intervals.py
@@ -0,0 +1,72 @@
+'''
+Find All Intervals
+
+You are given an array of intervals.
+Each interval is defined as: (start, end). e.g. (2, 5)
+It represents all the integer numbers in the interval, including start and end. (in the example 2, 3, 4 and 5).
+Given the array of intervals find the smallest set of unique intervals that contain the same integer numbers, without overlapping.
+
+
+Input: [(1, 5), (2, 6)]
+Output: [(1, 6)]
+
+Input: [(2, 4), (5, 5), (6, 8)]
+Output: [(2, 8)]
+
+Input: [(1, 4), (6, 9), (8, 10)]
+Output: [(1, 4), (6, 10)]
+
+=========================================
+Sort the intervals (using the start), accessing order. After that just iterate the intervals
+and check if the current interval belongs to the last created interval.
+    Time Complexity:    O(N LogN)
+    Space Complexity:   O(1)
+'''
+
+
+############
+# Solution #
+############
+
+def find_all_intervals(intervals):
+    n = len(intervals)
+    if n == 0:
+        return []
+
+    # sort the intervals
+    intervals.sort(key=lambda interval: interval[0])
+    result = []
+    start, end = intervals[0]
+
+    for i in range(1, n):
+        # check if this interval belongs to the last created interval
+        if intervals[i][0] <= end + 1:
+            # only the end can be changed (start is min, because array is sorted)
+            end = max(end, intervals[i][1])
+        else:
+            # save this interval
+            result.append((start, end))
+            # create a new interval
+            start, end = intervals[i]
+
+    # add the last interval
+    result.append((start, end))
+
+    return result
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => [(1, 6)]
+print(find_all_intervals([(1, 5), (2, 6)]))
+
+# Test 2
+# Correct result => [(2, 8)]
+print(find_all_intervals([(2, 4), (5, 5), (6, 8)]))
+
+# Test 3
+# Correct result => [(1, 4), (6, 10)]
+print(find_all_intervals([(1, 4), (6, 9), (8, 10)]))
diff --git a/Lists/min_swaps.py b/Lists/min_swaps.py
@@ -0,0 +1,56 @@
+'''
+Min Swaps
+
+You have a list of numbers and you want to sort the list.
+The only operation you have is a swap of any two arbitrary numbers.
+Find the minimum number of swaps you need to do in order to make the list sorted (ascending order).
+- The array will contain N elements
+- Each element will be between 1 and N inclusive
+- All the numbers will be different
+
+Input: [4, 1, 3, 2]
+Output: 2
+Output explanation: swap(4, 1) = [1, 4, 3, 2], swap(4, 2) = [1, 2, 3, 4]
+
+=========================================
+According to the description, all elements will have their position in the array,
+for example, K should be located at K-1 in the array.
+Itterate the array and check if each position has the right element,
+if not, put that element in the right position and check again.
+    Time Complexity:    O(N)    , the solution looks like O(N^2) but that's not possible, at most O(2*N) operations can be done
+    Space Complexity:   O(1)
+'''
+
+
+############
+# Solution #
+############
+
+def min_swaps(a):
+    n = len(a)
+    swaps = 0
+
+    for i in range(n):
+        # swap the elements till the right element isn't found
+        while a[i] - 1 != i:
+            # swap the elements
+            tmp = a[a[i] - 1]
+            a[a[i] - 1] = a[i]
+            a[i] = tmp
+
+            swaps += 1
+
+    return swaps
+
+
+###########
+# Testing #
+###########
+
+# Test 1
+# Correct result => 2
+print(min_swaps([4, 1, 3, 2]))
+
+# Test 2
+# Correct result => 3
+print(min_swaps([4, 1, 2, 3]))
