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.