Untitled
unknown
plain_text
a year ago
1.3 kB
4
Indexable
// pseudo code
fn(intervals)
{
sort(intervals,(a,b)->{
if(a[0] == b[0])
{
if(a[1] == b[1])
{
return a[2] - b[2];
// Integer.comapre(a[2],b[2]);
}
else
{
return Integer.comapre(a[1],b[1]);
}
}
else
{
return Integer.comapre(a[0],b[0]);
}
return a[0] - b[0];
});
stime = intervals[0][0];
maxreach = stime + intervals[i][1];
res.add(intervals[0][2]); // index
idx = 1 ; // points to array
while(idx<n && intervals[idx][0]<=maxReach)
{
minheap.add({idx,intervals[idx][1]});
idx++;
}
while(!minheap.isempty() || idx<n)
{
if(!minheap.isEmpty())
{
int[] x = minheap.poll();
st = x.start;
maxReach = st+x.duration;
res.add(x[2]); // add index inrres
while(idx<n && intervals[idx][0]<=maxReach)
{
minheap.add({idx,intervals[idx][1]});
idx++;
}
}
else
{
st = intervals[idx][0];
maxReach = intervals[idx][1] + st;
res.add(intervalsp[idx][2]);
while(idx<n && intervals[idx][0]<=maxReach)
{
minheap.add({idx,intervals[idx][1]});
idx++;
}
}
}
return res;
}
Editor is loading...
Leave a Comment