subject

Solving problems

This question is very touching, the last final exam is just in progress, my review (preview) is also in progress, I am a kid who often skips classes (...)

How do you review at the end of the term?
We must first review the subjects that are closest to the exam time. This topic gives you review time for only one subject at a time, without interruption, and then gives you review time for each subject. This results in that if some subjects are close to DDL, but if we review them, we will be unable to complete the review for others.

Examples are as follows:

Assuming that the duration s array is such a linear algebra in college physics [2,4] higher mathematics [5,7] [3,3], strategically, we will try to study linear algebra first. Then I tried College physics, and at this time we found that I couldn't take college physics after I even took linear algebra. Can only give up; There wasn't enough time for me to switch to higher mathematics.

What is the reasonable way to do that? That's when we need to give up linear algebra, because the weights of linear algebra and college physics are indistinguishable. Since only one of them can be built, we should make the current cumulative time spent less. Although ddl is later in college physics than linear algebra, it also takes less time to study. If we've given up a course, we'll give up for a longer time.

Summary:

1. Let's review DDL for a while.
2. If the review time exceeds DDL, you need to optimize, abandon the most time-consuming subjects you have previously selected, and replace them with the current one to reduce the current time-consuming ones! (This precondition is based on the preference for DDL, because once the overrun is generated in time order, it will certainly take less time to replace with the previous maximum, so it will not exceed DDL)

Problem solving code

According to the solution ideas, the writing ideas of the code are drawn:

1. Priority Review DDL Nearest ->Sort it from smallest to largest using DDL.
2. Replacement beyond DDL --> Operate with a priority queue.

cpp solution

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        sort(courses.begin(), courses.end(), [](const auto& a, const auto& b) { return a[1] < b [1];});

        priority_queue<int> q;
        int day = 0;
        for (const auto& c: courses) {
            if (day + c[0] <= c[1]) {
                day += c[0];
                q.push(c[0]);
                continue;
            }
            if (!q.empty() && q.top() > c[0]) {
                day -= q.top();
                day += c[0];
                q.pop();
                q.push(c[0]);
            } 
            
        }

        return q.size();
    }
};

The go language is a bit cumbersome, and you need to implement some interfaces to use Heap

go lang

func scheduleCourse(courses [][]int) int {
    sort.Slice(courses, func(i, j int) bool {
        return courses[i][1] < courses[j][1]
    })

    h := &IntHeap{}
    total := 0 // Total time for all courses in the priority queue
    for _, course := range courses {
        if t := course[0]; total+t <= course[1] {
            total += t
            heap.Push(h, t)
        } else if h.Len() > 0 && t < (*h)[0] {
            total += t - (*h)[0]
            heap.Pop(h)
            heap.Push(h,t)
        }
    }
    return h.Len()
}

type IntHeap []int  // Define a type

func (h IntHeap) Len() int { return len(h) }  // Bind len method, return length
func (h IntHeap) Less(i, j int) bool {  // Bind less method
	return h[i] > h[j]  // If h[i]<h[j] generates a small root heap, if h[i]>h[j] generates a large root heap
}
func (h IntHeap) Swap(i, j int) {  // Bind swap method, swap two element positions
	h[i], h[j] = h[j], h[i]
}

func (h *IntHeap) Pop() interface{} {  // Bind the pop method, take an element from the end, and return
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func (h *IntHeap) Push(x interface{}) {  // Bind push method, insert new element
	*h = append(*h, x.(int))
}