package BinarySearch;
import java.io.*;
import java.util.*;
public class JobScheduling {
static int N, D, M;
static ArrayList<Group> arr;
public static void main(String[] args) throws IOException{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter pw = new PrintWriter(System.out);
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
D = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new ArrayList<Group>();
st = new StringTokenizer(br.readLine());
for(int i = 0; i < M; i++) {
arr.add(new Group(Integer.parseInt(st.nextToken()), i+1));
//System.out.println(arr[i]);
}
Collections.sort(arr);
int a = 0, b = M;
while(a!=b) {
int mid = (a+b)/2;
if(works(mid)) {
b=mid;
}else {
a=mid+1;
}
//System.out.println(a+" "+ b);
}
pw.println(a);
/*
int point1 = 0;
for(int i = 0; i < N; i++) {
int curr = point1 + a;
while(point1 < M && point1 < curr) {
pw.print(arr.get(point1).b + " ");
point1++;
}
pw.println("0");
}
*/
//System.out.println(a);
//pw.println(a);
}
private static boolean works(int mid) {
// TODO Auto-generated method stub
int prevDay[] = new int[mid];
for(int i = 0; i < M;) {
for(int j = i; j < i +mid; j++) {
if(j >= M) {
break;
}
if(arr.get(j).a> prevDay[j-i]) {
prevDay[j-i] = arr.get(j).a;
}else {
int temp = prevDay[j-i]-arr.get(j).a+1;
if(temp > D) {
return false;
}
prevDay[j-i] = temp+prevDay[j-i];
}
}
i+=mid;
if(i >= M) {
break;
}
}
return true;
}
public static class Group implements Comparable<Group> {
int a,b;
// Constructor
public Group(int a, int b) {
this.a = a;
this.b = b;
}
public String toString()
{
return this.a + " " + this.b;
}
@Override
public int compareTo(Group other) {
return (int) (a-other.a);
}
@Override
public boolean equals(Object other) {
Group that = (Group) other;
return that.b ==b;
}
}
}
Compilation message
jobs.java:7: error: class JobScheduling is public, should be declared in a file named JobScheduling.java
public class JobScheduling {
^
1 error
