CareerCup

I'd do something like this:

1. Store the intervals as nodes of a doubly-linked list. Each node contains from_, to_, val_, id_. id_ is uint32_t, unique among the nodes.

2. For each node in the linked list, dump into a min heap abs difference of the node's value and the node's next node's value. The min heap's element consists of the difference and uint64_t id, which is built out of the 2 linked list nodes' ids.

3. The min heap is updatable. I.e. it's possible to update or remove a node of it by id.

4. Get the top element from the heap, parse id of the element into ids of 2 linked list nodes, get pointers to the nodes using the ids.

5. Merge the 2 nodes, update value of the first node with average of the node's values, remove the second node from the linked list.

6. Update the min heap. I.e. remove the heap node with id equal to "second_linked_list_node->next_to_second_linked_list_node", update value of the heap node with id equal to "prev_to_first_linked_list_node->first_linked_list_node", and insert a new heap node, having id "first_linked_list_node->next_to_second_linked_list_node".

O(n) space, O(nlogn) time

Using min heap(priority queue) and array

#include <iostream>
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
class Point
{
	public: 
		int value;
		int start;
		int end;
};
class myComparator 
{ 
	public: 
	    int operator() (const Point* a, const Point* b) 
	    { 
	        return a->value > b->value; 
	    } 
};
int mod(int a)
{
	return a < 0 ? (-1 * a) : a;
}
void MergeIntervals(int* a, int n, int threshold)
{
	int parent[n];
	for(int i=0; i<n; i++)
	{
		parent[i] = i;
	}
	priority_queue<Point*, vector<Point*>, myComparator> pq;
	int min1 = mod(a[0] - a[1]);
	int min2 = INT_MAX;
	int a1 = 0;
	int a2;
	for(int i=1; i<n-1; i++)
	{
		if(mod(a[i] - a[i+1]) <= min1)
		{
			a2 = a1;
			a1 = i;
			min1 = mod(a[i] - a[i+1]);
			min2 = min1;
		}
		else if(mod(a[i] - a[i+1]) <= min2)
		{
			a2 = i;
			min2 = mod(a[i] - a[i+1]);
		}
	}
	if(a1 == a2+1 || a2 == a1+1)
	{
		int min = INT_MAX;
		for(int i=0; i<n-1; i++)
		{
			int x = mod(a[i] - a[i+1]);
			if(x < min && x != min1 && x != min2)
			{
				a2 = i;
				min = x;
			}
		}
		min2 = min;
	}
	
	cout<<"a1 "<<a1<<endl;
	cout<<"a2 "<<a2<<endl;
	Point* p1 = new Point();
	p1->value = min1;
	p1->start = a1;
	p1->end = a1+1;
	
	Point* p2 = new Point();
	p2->value = min2;
	p2->start = a2;
	p2->end = a2+1;
	
	pq.push(p1);
	pq.push(p2);
	
	while(pq.size() != 1 && pq.top()->value <= threshold)
	{
		Point* p = pq.top();
		pq.pop();
		int startParent = p->start;
		int endParent = p->end;
		a[startParent] = (a[p->start] + a[p->end])/2;
		a[endParent] = a[startParent];
		parent[startParent] = endParent;
		parent[endParent] = startParent;
		
		Point* new_p = new Point();
		int diff1 = INT_MAX;
		int diff2 = INT_MAX;
		if(startParent > 0)
		{
			diff1 = mod(a[startParent-1] - a[startParent]);
		}
		if(endParent < n-1)
		{
			diff2 = mod(a[endParent+1] - a[endParent]);
		}
		if(diff1 != INT_MAX || diff2 != INT_MAX)
		{
			if(diff1 < diff2)
			{
				Point* p_new = new Point();
				p_new->value = diff1;
				p_new->start = parent[startParent-1];
				p_new->end = parent[startParent];
			}
			else
			{
				Point* p_new = new Point();
				p_new->value = diff2;
				p_new->start = parent[endParent];
				p_new->end = parent[endParent+1];
			}
		}
	}
	
	int i =0;
	while(i < n)
	{
		cout<<i<<" "<<parent[i];
		i = parent[i] + 1;
		cout<<endl;
	}
	
}
int main() {
	int n;
	cin>>n;
	int a[n];
	for(int i=0; i<n; i++)
	{
		cin>>a[i];
	}
	int t;
	cin>>t;
	MergeIntervals(a, n, t);
}