\documentclass[11pt]{article}
\usepackage{amsmath, amssymb, amsfonts}
\usepackage[margin=1in]{geometry}
\usepackage{fancyhdr}
\usepackage{tcolorbox}
\usepackage{enumerate}
\usepackage{tikz}

\usepackage{algorithmic}

    \setlength{\headheight}{26pt}
    \pagestyle{fancy}
    \fancyhead[C]{\textbf{Basic Algorithms (Section 7)}\\Fall 2024}
    \fancyhead[R]{HW6 (Due 10/30 22:00)\\ Instructor: Jiaxin Guan}
    \fancyfoot[C]{}
    \fancyfoot[R]{\thepage}
    \renewcommand{\headrulewidth}{0.4pt}
    \renewcommand{\footrulewidth}{0.4 pt}
    


 
\begin{document}


    %%%% EDIT THIS PART 
    %Put your name and Net ID here
    \fancyhead[L]{Name:  \\ Net ID: }
    %Write your collaborators' names here
    \fancyfoot[L]{Discussion Partners:}
    %%%%%
	
    
    \begin{tcolorbox}[title={Problem 1 (Interval Scheduling with Revenue, 40 pts)}] \setlength\parindent{1em}
        During the lecture we considered the activity selection/interval scheduling problem, where the goal is to schedule as many non-overlapping activities/intervals as possible. 
        
        Now suppose instead of maximizing the number of activities scheduled, we modify the problem by adding ``revenue'' value $r_i$ to each activity $I_i$, for all $i$. The modified goal is to find a set of non-overlapping activities $S'\subseteq S$ that maximizes the total revenue, defined as \[
        \sum_{I_i\in S'} r_i.\]

        \begin{enumerate}[(a)]
        \item (20 pts) Does the greedy algorithm presented in class correctly solve
        this problem? If yes, provide a brief justification. If no, provide a counterexample.
        \item (20 pts) What about the improved DP algorithm (the one with $O(n\log n)$ runtime) presented in class? Can it be easily adapted to solve this problem? If yes, briefly describe what changes need to be made. If no,  provide a brief justification.
        \end{enumerate}
            
    \end{tcolorbox}
    %Write your solution here!


    \newpage


    %Problem 2
    \begin{tcolorbox}[title={Problem 2 (Min Interval Scheduling, 60 pts)}] \setlength\parindent{1em}
        In the interval scheduling problem, we are given a set of intervals $S=\{[s_1, f_1],\dots,[s_n,f_n]\}$ and we want to find the largest subset $S'\subseteq S$ such that no two intervals in $S'$ overlap. 

        Now suppose that instead of wanting to prevent overlap, we want to prevent having any empty areas. That is, we want that for every point $p \in [a, b]$, there is some interval $I = [s,f] \in S'$ such that $s \leq p \leq f$. We say that such a set $S'$ \emph{covers} $[a,b]$.
        
        For example, on input $S = \{[0,5], [2,6], [3, 8], [7, 10], [9, 10]\}$, with target $[a,b] = [0, 10]$ an optimal covering is $S' = \{[0,5], [3,8], [7, 10]\}$.
        
        Given a set of $n$ intervals $S$ and a target interval $[a,b]$, we want to construct an efficient greedy algorithm to find the smallest $S' \subseteq S$ such that $S'$ covers $[a,b]$.
        
        \begin{enumerate}[(a)]
            \item (15 pts) Consider the greedy strategy where we always choose the interval $I$ which covers the largest amount of uncovered area of the target interval. Construct a counterexample such that this greedy strategy leads to a suboptimal solution.
            \item (30 pts) Give a greedy strategy that is safe. Prove that your greedy choice combined with an optimal solution to the subproblem remaining (after you make your greedy choice) is an optimal solution to the problem.
            \item (15 pts) Describe a full algorithm that implements your greedy strategy and analyze its running time. For full credit, your algorithm should run in time $O(n\log n)$.
        \end{enumerate}
    \end{tcolorbox}
    %Write your solution here!
       
\end{document}