Solve swaps, graph paths, and movie DP

Design and implement solutions for three tasks derived from a HackerRank-style assessment.

1. Minimum swaps to reverse sort an array:

• Input: an integer array A of length n with distinct values. Allowed operation: swap any two indices i and j; each swap costs 1.
• Output: the minimum number of swaps needed to reorder A into strictly descending order.
• Requirements: Provide an O(n log n) approach (e.g., sort with index mapping and cycle decomposition/greedy). Prove correctness and analyze time/space. Briefly note how you would adapt if duplicates can appear.

2. Enumerate simple paths in a graph via backtracking:

• Input: an undirected graph G = (V, E) with vertices labeled 0..n-1, and two vertices s and t.
• Task: return all simple paths from s to t (no vertex repeats) using backtracking. If the number of paths is huge, return the count and support streaming/yielding paths.
• Requirements: Prevent cycles with visited sets, discuss pruning heuristics (e.g., degree bounds, early exits), and analyze worst-case time/space complexity.

3. Movie ratings scheduling using bottom-up DP (weighted interval scheduling):

• Input: m movies; each movie i has start time s_i, end time e_i (e_i > s_i), and rating w_i.
• Task: choose a subset of non-overlapping movies maximizing total rating.
• Requirements: Provide an O(m log m) bottom-up DP: sort by end time, compute p(i) (the rightmost movie that finishes before s_i), define DP[i] = max(DP[i-1], DP[p(i)] + w_i), reconstruct one optimal set, and analyze complexity. Explain why naive backtracking is exponential and would time out.