1851-Minimum-Interval-to-Include-Each-Query.java

classQuery {

intindex;
intqueryTimeStamp;
intresult;

publicQuery(intindex, intqueryTimeStamp) {
this.index = index;
this.queryTimeStamp = queryTimeStamp;
this.result = -1; // initially store as -1
 }

@Override
publicStringtoString() {
return"[" + index + "," + queryTimeStamp + "," + result + "]";
 }

publicvoidsetResult(intresult) {
this.result = result;
 }
}

classIntervalComparatorimplementsComparator<int[]> {

publicstaticintgetSize(int[] interval) {
return (interval[1] - interval[0] + 1);
 }

@Override
publicintcompare(int[] o1, int[] o2) {
into1Size = getSize(o1), o2Size = getSize(o2);
if (o1Size != o2Size) {
return (o1Size - o2Size);
 }
return (o1[1] - o2[1]);
 }
}

classSolution {

publicint[] minInterval(int[][] intervals, int[] queries) {
// book-keeping & sorting
intnumIntervals = intervals.length;
intnumQueries = queries.length;

// Sort by start times
Arrays.sort(intervals, (o1, o2) -> (o1[0] - o2[0]));

Query[] sortedQueries = newQuery[numQueries];
for (inti = 0; i < numQueries; i++) sortedQueries[i] =
newQuery(i, queries[i]);

Arrays.sort(
sortedQueries,
 (q1, q2) -> (q1.queryTimeStamp - q2.queryTimeStamp)
 );

// algorithm

Comparator<int[]> comparator = newIntervalComparator();
PriorityQueue<int[]> pq = newPriorityQueue<>(comparator);
intidx = 0;

for (Queryquery : sortedQueries) {
// 1. Keep taking all those queries which have lower starting time than the query time and add them to priority queue
while (
 (idx < numIntervals) &&
 (query.queryTimeStamp >= intervals[idx][0])
 ) {
pq.add(intervals[idx]);
idx++;
 }

// 2. Keep removing the inconsistent intervals and get the min size interval from priority queue
while (!pq.isEmpty() && (pq.peek()[1] < query.queryTimeStamp)) {
pq.remove();
 }

// Now, priority queue must have the consistent & smallest interval
intans = pq.isEmpty() ? -1 : IntervalComparator.getSize(pq.peek());
query.setResult(ans);
 }

// reconversion
int[] results = newint[numQueries];
for (Queryquery : sortedQueries) {
results[query.index] = query.result;
 }

returnresults;
 }
}