1665. 完成所有任务的最少初始能量-快速排序+贪心算法

1665. 完成所有任务的最少初始能量-快速排序+贪心算法

给你一个任务数组 tasks ，其中 tasks[i] = [actuali, minimumi] ：

actuali 是完成第 i 个任务 需要耗费 的实际能量。
minimumi 是开始第 i 个任务前需要达到的最低能量。
1
2

比方说，如果任务为 [10, 12] 且你当前的能量为 11 ，那么你不能开始这个任务。如果你当前的能量为 13 ，你可以完成这个任务，且完成它后剩余能量为 3 。

你可以按照 任意顺序 完成任务。

请你返回完成所有任务的 最少 初始能量。

示例 1：

输入：tasks = [[1,2],[2,4],[4,8]]
输出：8
解释：
一开始有 8 能量，我们按照如下顺序完成任务：
- 完成第 3 个任务，剩余能量为 8 - 4 = 4 。
- 完成第 2 个任务，剩余能量为 4 - 2 = 2 。
- 完成第 1 个任务，剩余能量为 2 - 1 = 1 。
注意到尽管我们有能量剩余，但是如果一开始只有 7 能量是不能完成所有任务的，因为我们无法开始第 3 个任务。

示例 2：

输入：tasks = [[1,3],[2,4],[10,11],[10,12],[8,9]]
输出：32
解释：
一开始有 32 能量，我们按照如下顺序完成任务：
- 完成第 1 个任务，剩余能量为 32 - 1 = 31 。
- 完成第 2 个任务，剩余能量为 31 - 2 = 29 。
- 完成第 3 个任务，剩余能量为 29 - 10 = 19 。
- 完成第 4 个任务，剩余能量为 19 - 10 = 9 。
- 完成第 5 个任务，剩余能量为 9 - 8 = 1 。

示例 3：

输入：tasks = [[1,7],[2,8],[3,9],[4,10],[5,11],[6,12]]
输出：27
解释：
一开始有 27 能量，我们按照如下顺序完成任务：
- 完成第 5 个任务，剩余能量为 27 - 5 = 22 。
- 完成第 2 个任务，剩余能量为 22 - 2 = 20 。
- 完成第 3 个任务，剩余能量为 20 - 3 = 17 。
- 完成第 1 个任务，剩余能量为 17 - 1 = 16 。
- 完成第 4 个任务，剩余能量为 16 - 4 = 12 。
- 完成第 6 个任务，剩余能量为 12 - 6 = 6 。

事实上，我们总是可以通过贪心算法，来获得一个刚刚好可以满足一个我们任意给定序列的能量值，这一题有相关的数学论证，博主看了下，还是很棒的，感兴趣可以去学习一下，解题代码如下：

void quick(int **a,int low,int high){
    if(low<high){
        int l=low,h=high,p=a[low][0],p1=a[low][1],pz=a[low][1]-a[low][0];

        while(low<high){
            while(low<high&&a[high][1]-a[high][0]<=pz){
                high--;

            }
            a[low][1]=a[high][1];
            a[low][0]=a[high][0];
            while(low<high&&a[low][1]-a[low][0]>=pz){
                low++;
            }
            a[high][1]=a[low][1];
            a[high][0]=a[low][0];
        }
        a[low][1]=p1;
         a[low][0]=p;
        quick(a,l,low-1);
        quick(a,low+1,h);
    }
}

int comp(const void *a, const void *b)
{
   int x = (*(int**)a)[1] - (*(int**)a)[0];
   int y = (*(int**)b)[1] - (*(int**)b)[0];
   if (x != y) {
       return y - x;
   } else {
       return (*(int**)b)[0] - (*(int**)a)[0];
   }
}

int max(int a, int b)
{
    return a > b ? a : b;
}

int minimumEffort(int** tasks, int tasksSize, int* tasksColSize){
    
  
    qsort(tasks, tasksSize, sizeof(int*), comp);

  
    int start=tasks[0][1];
    int restart=start;
    int add=0;
    
    for(int i=1;i<tasksSize;i++){
      
        start=start-tasks[i-1][0];
        
        if(start<tasks[i][1]){
            add=tasks[i][1]-start+add;
            start=tasks[i][1];
        }
      

    }
    return add+restart;

   

}





















1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87