4. (15分) We have a set of n open intervals S = \(ai, bi): i = 1, , n\. We want to choose a largest subset S' S such that the selected intervals in S' are mutually disjoint. Please give an O(nlog n)-time algorithm to solve this problem.

6. (10 分) 使用 linked list 實作 stack，運用以下 C 語言程式：typedef struct node { int value; node *next;}void push (node **top, int new_value) { // assume top is not nullnode new_node = (node ) malloc (sizeof (node));// 實作以下敘述// add new_node to stack by top}int pop (node **top) { // assume top is not nullint value;node deleting_node = top;// 實作以下敘述// remove the deleting node from stack, get the value of deleting nodefree(deleting_node);return value;}

4. (15分) We have a set of n open intervals \( S = \{(ai, bi): i = 1, \dots, n\} \). We want to choose a largest subset \( S' \subseteq S \) such that the selected intervals in \( S' \) are mutually disjoint. Please give an O(nlog n)-time algorithm to solve this problem.

相關申論題

相關試卷