Questions: Given an
array of ranges, please merge the overlapping ones. For example, four ranges
[5, 13], [27, 39], [8, 19], [31, 37] (in blue in Figure1) are merged into
two ranges, which are [5, 19] and [27, 39] (in green in Figure 1).
![]() |
Figure 1: Merge four ranges [5, 13], [27, 39], [8, 19] and [31, 37] (in blue), and get [5, 19], and [27, 39] (in green) |
Analysis: Before we
analyze how to merge an array of ranges, let’s discuss how to merge two ranges.
When two ranges don’t overlap each other, they can’t merge. When two ranges
overlap, the less starting value of two ranges becomes the starting value of
the merged range, and the greater ending value of two ranges becomes the ending
value of the merged range.
Therefore,
two ranges [5, 13] and [8, 19] are merged into a new range [5, 19], and two
ranges [27, 39] and [31, 37] are merged into a new range [27, 39]. The two
merged ranges can’t be merged further because they don’t overlap.
The
next question is: How to check whether two ranges overlap each other? When
two ranges overlap, there is at least on node in a range is contained in the
other range. For instance, the starting value 8 of the range [8, 19] is
contained in the range [5, 13], therefore, the two ranges [5, 13] and [8, 19]
overlap. No nodes in the range [8, 19] are contained in the range [31, 37], so
the two ranges don’t overlap.
The
following code shows how to merge two ranges, as well as to check whether two
ranges overlap:
public bool Contains(int value)
{
if (value >= this.Start && value <= this.End)
{
return true;
}
return false;
}
public bool Overlaps(Range other)
{
if (other == null)
{
return false;
}
if (this.Contains(other.Start) || this.Contains(other.End)
|| other.Contains(this.Start) || other.Contains(this.End))
|| other.Contains(this.Start) || other.Contains(this.End))
{
return true;
}
return false;
}
public Range Merge(Range other)
{
if (!this.Overlaps(other))
{
throw new ApplicationException("Can't merge two
ranges.");
}
int newStart = (this.Start < other.Start) ? this.Start : other.Start;
int newEnd = (this.End > other.End) ? this.End : other.End;
return new Range(newStart, newEnd);
}
Now
let’s move on to merge an array of ranges.
The first step is to sort the ranges based on their start values. When
the ranges [5, 13], [27, 39], [8, 19], and [31, 37] are sorted, they are in the
order of [5, 13], [8, 19], [27, 39], and [31, 37].
The
next steps are to merge the sorted ranges. The merged ranges are inserted into
a data container. At each step, a range is retrieved from the sorted array, and
merged with the existing ranges in the container.
At
first the data container is empty, and the first range [5, 13] is inserted into
the container directly, without merging. Now there is only one range [5, 13] in
the container.
Then
the next range [8, 19] is retrieved. Since it overlaps the range[5, 13], and
they become [5, 19] when they merged. There is still only one range, which is [5,
19] in the container.
The
next range [27, 39] is retrieved, which does not overlap the range [5, 19] in
the container, so it is inserted into the range directly without merging. There
are two ranges [5, 19] and [27, 39] in the container.
The
last range in the sorted array is [31, 37]. It overlaps the last range [27, 39] in the container.
Therefore, the last range [27, 39] is deleted from the container, and then the
merged range is inserted into the container. At this step, the merged range is
also [27, 39].
Ranges
in the container are also sorted based on their starting values, and they don't
overlap each other. Notice that it's only necessary to check whether the new
range overlap the last range in the container. Why not the other ranges in the
container? Let's analyze what would happen when a new range in the sorted array
overlap two ranges in the container, with Figure 2:
![]() |
Figure 2: It causes problems when a new range overlaps two ranges in the merged container |
In
Figure 2, the container has two ranges A and B, and a new range C is retrieved
from the sorted array, which overlaps the ranges A and B. Since C overlaps A,
the starting value of C should be less than the ending value of A. On the other
hand, C is retrieved from the sorted array later than B, the starting value of
C is greater than starting value of B. Additionally, B is behind A and they
don't overlap, so the starting value of B is greater than the ending value A.
Therefore, the starting value of C is greater than the ending value of A. It
contradicts.
Since
it's only necessary to merge new ranges from the sorted array with the last
range in the container. We implement the container as a stack, and the last
range is on the top of the stack.
The
following is the C# code to merge a sort an array of ranges:
public static Range[]
Merge(Range[] ranges)
{
Stack<Range> results = new Stack<Range>();
if (ranges != null)
{
Array.Sort(ranges, CompareRangeByStart);
foreach (var range in ranges)
{
if (results.Count == 0)
{
results.Push(range);
}
else
{
var top =
results.Peek();
if
(top.Overlaps(range))
{
var union = top.Merge(range);
results.Pop();
results.Push(union);
}
else
{
results.Push(range);
}
}
}
}
return results.Reverse().ToArray();
}
The
code with unit tests are shared at http://ideone.com/kg4TwM.
More coding interview questions are discussed
in my book< Coding Interviews: Questions, Analysis & Solutions>. You
may find the details of this book on Amazon.com,
or Apress.
The author Harry He
owns all the rights of this post. If you are going to use part of or the whole
of this ariticle in your blog or webpages, please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books,
please contact him via zhedahht@gmail.com . Thanks.
The current method returns incorrect range after merging [5,13] , [27,39] giving [5,39]
ReplyDeletepublic Range Merge(Range other)
{
if (!this.Overlaps(other))
{
throw new ApplicationException("Can't merge two ranges.");
}
int newStart = (this.Start < other.Start) ? this.Start : other.Start;
int newEnd = (this.End > other.End) ? this.End : other.End;
return new Range(newStart, newEnd);
}
the correct statement for the new end code statement is
int newEnd = (this.End > other.Start) ? this.End : other.End;
let me know if i am wrong in understanding problem..
The two ranges [5, 13] and [27, 39] don't overlap, and they will not merge.
DeleteThe results of my code to merge [5, 13] and [27, 39] contains the same two ranges. A new test cases Test6 is added, please refer to the source code unit test at http://ideone.com/kg4TwM. Thanks.
Ohayo,
DeleteBrilliant article, glad I slogged through the it seems that a whole lot of the details really come back to from my past project.
Currently retrieving account attributes
We are currently in the process of retrieving your account attributes. Please try again in a few minutes.
I am getting this error message for the last couple of days. According to it is about my account not AWS Training been activated. But according to am email from Amazon, my account is fully activated.
Anyways great write up, your efforts are much appreciated.
Ganesh,
Glad to have found your site. Keep up the good work! DB Product Review
ReplyDeleteyou can take more help and challenge from quiz questions at:- http://www.fixoncloud.com/Home/Quiz/
ReplyDeleteIt will prepare you for many languages.
hmm like this...
ReplyDeletetest Cara Ngoding
Nice Website...
ReplyDeleteHey JOIN now fblikesbot.com and Increase Facebook Likes your profile and websites.
Increase Facebook Likes and check your website worth worth my websites
its may be very beneficial for you also really
Nice blog...providing lot of information about Jobs and Results
ReplyDeleteThanks for your sharing. I also discuss this problem here http://www.capacode.com/array/merge-ranges/ :)
ReplyDeleteProgramming is very interesting and creative thing if you do it with love. Your blog code helps a lot to beginners to learn programming from basic to advance level. I really love this blog because I learn a lot from here and this process is still continuing.
ReplyDeleteLove from Pro Programmer
Programming is combination of intelligent and creative work. Programmers can do anything with code. The entire Programming tutorials that you mention here on this blog are awesome. Beginners Heap also provides latest tutorials of Programming from beginning to advance level. Be with us to learn programming in new and creative way.
ReplyDeleteGood questions for practicing and preparing for an interview, thanks! They're unlikely to be used in a actual interview though, considering they've become too common and are easily available online. Companies now either create their own questions or use an online platform that does the same, for example: https://www.testdome.com/
ReplyDelete
ReplyDeletenice
http://www.kuwait.prokr.net/satellite-indian-region-of-the-tenth/
http://www.kuwait.prokr.net/
Thanks for sharing
ReplyDeletewebsite design siliguri
عروض على التكييفات من يونيو اير
ReplyDeleteعروض على تكييفات 2017
اسعار تكييفات 2016
اسعار تكييفات 2017
اسعار تكييفات 2018
عنوان مبيعات يونيو اير
5شارع عامر امين القومية العربية بجوار الدائري
12561 إمبابة
مبيعات يونيو اير
يونيون اير
صيانة يونيون اير
تكييف يونيون اير
تكييف يونيون اير
خدمة عملاء يونيون ايرجروب
رقم خدمة عملاء unionaire
شركة يونيون اير
تكيفات يونيون ايير
اسعار تكيفات يونيون ايير
شاشات يونيون اير
رقم يونيون اير 19058
صيانة unionaire
توكيل يونيون اير
تكييفات بالتقسيط
تكييفات يونيون اير
الخطوط الارضية 0233580534/0233564318/0233564320/0233565322/0233564325/0233509275/023509267/0233509268
عنوان مبيعات شارب
4شارع عامر امين القومية العربية بجوار الدائري
12561 إمبابة
مبيعات شارب
شارب
صيانة شارب
تكييف شارب
سعر تكييف شارب
خدمة عملاء شارب
رقم خدمة عملاء شارب
شركة شارب
تكيفات شارب
اسعار تكييفات شارب
شاشات شارب
رقم شارب 19058
صيانة شارب
توكيل شارب
تكييفات بالتقسيط
تكييفات شارب
مبيعات شارب
الخطوط الارضية 0233580534/0233564318/0233564320/0233565322/0233564325/0233509275/023509267/0233509268
ReplyDeleteاسعار تكييفات 2016
اسعار تكييفات 2017
اسعار تكييفات 2018
عنوان مبيعات يونيو اير
5شارع عامر امين القومية العربية بجوار الدائري
12561 إمبابة
مبيعات يونيو اير
يونيون اير
صيانة يونيون اير
تكييف يونيون اير
تكييف يونيون اير
خدمة عملاء يونيون ايرجروب
رقم خدمة عملاء unionaire
شركة يونيون اير
تكيفات يونيون ايير
اسعار تكيفات يونيون ايير
شاشات يونيون اير
رقم يونيون اير 19058
صيانة unionaire
توكيل يونيون اير
تكييفات بالتقسيط
تكييفات يونيون اير
الخطوط الارضية 0233580534/0233564318/0233564320/0233565322/0233564325/0233509275/023509267/0233509268
عنوان مبيعات شارب
4شارع عامر امين القومية العربية بجوار الدائري
12561 إمبابة
مبيعات شارب
شارب
صيانة شارب
تكييف شارب
سعر تكييف شارب
خدمة عملاء شارب
رقم خدمة عملاء شارب
شركة شارب
تكيفات شارب
اسعار تكييفات شارب
شاشات شارب
رقم شارب 19058
صيانة شارب
توكيل شارب
تكييفات بالتقسيط
تكييفات شارب
مبيعات شارب
الخطوط الارضية 0233580534/0233564318/0233564320/0233565322/0233564325/0233509275/023509267/0233509268
Thanks for sharing fabulous information on related to career. It's my pleasure to read related to search jobs .I have also bookmarked you for checking out new posts.
ReplyDeleteNice Blog, I really wonder to visit your blog, Thanks a lot! for sharing the useful Information.
ReplyDeleteiphone job Oriented course
apple ios training institutes Hyderabad
Hello Mate,
ReplyDeleteI’ve often thought about this No. 54 - Merge Ranges . Nice to have it laid out so clearly. Great eye opener.
I am using an EC2 instance, my application on the instance is working fine I mean the website hosted on EC2 instance but when I expose it to the general users it gets hacked. The hacking team is from Indonesia and I am unable to identify what type of hacking technique is it. I cannot find their ip in the log file of SSH and a new file is uploaded to the EC2 Instance. AWS Training
Very useful article, if I run into challenges along the way, I will share them here.
Thanks,
Ajeeth
Aloha,
ReplyDeleteZoooooooom! That’s how speedy and easy this read was! Looking forward to more of such powerful content on No. 54 - Merge Ranges
I'm currently having a small problem with my ECS setup, and I've posted about it here in the ECS forum but still waiting for a response. As I would like to get this issue resolved quickly (and I suspect it's an AWS bug) I would have preferred to open a support case to have someone look at it and quickly tell me either what I did wrong or that the bug is being fixed. AWS Training USA
Thank you very much and will look for more postings from you.
Ciao,
Ajeeth
ReplyDeleteHi Your Blog is very nice!!
Get All Top Interview Questions and answers PHP, Magento, laravel,Java, Dot Net, Database, Sql, Mysql, Oracle, Angularjs, Vue Js, Express js, React Js,
Hadoop, Apache spark, Apache Scala, Tensorflow.
Mysql Interview Questions for Experienced
php interview questions for freshers
php interview questions for experienced
python interview questions for freshers
tally interview questions and answers
Thanks for the information.I really need that information.It's helps me to learn new things. I want to be like you. keep posting new article . I'm your fan. I love to read your article .
ReplyDeletehttp://www.tutorialabc.com/2018/04/c-interview-questions.html
ReplyDeleteاسقف معلقه جبس بالرياض شركة سحر اللمسات
ReplyDeleteشركة تشطيبات داخلية بالرياض-شركة تشطيبات خارجيه بالرياض- شركة تشطيبات مكاتب وقصور بالرياض شركة تشطيب فلل بالرياض -
ReplyDeleteشركة ترميم فلل وقصور بالرياض من أفضل شركات الترميم
ReplyDeleteHi Your Blog is very nice!!
Get All Top Interview Questions and answers PHP, Magento, laravel,Java, Dot Net, Database, Sql, Mysql, Oracle, Angularjs, Vue Js, Express js, React Js,
Hadoop, Apache spark, Apache Scala, Tensorflow.
Mysql Interview Questions for Experienced
php interview questions for freshers
php interview questions for experienced
python interview questions for freshers
tally interview questions and answers
codeingniter interview questions
cakephp interview questions
express Js interview questions
react js interview questions
laravel Interview questions and answers
ReplyDeleteتركيب حجر بالرياض
مجالس تراث بالرياض
محل ورق حائط بالرياض
tuyển sinh cao học 2018
ReplyDeletetuyển sinh thạc sĩ quản trị kinh doanh
thạc sĩ quản trị kinh doanh,
học thạc sĩ quản trị kinh doanh
tuyển sinh MBA
شركة نقل اثاث
ReplyDeleteCodingHoliday Camps - We provide the best online learning coaching for Stem Education Coding in Singapore. Get the best online Stem Education Coding for your kids.
ReplyDeleteThis comment has been removed by the author.
ReplyDeleteI’m planning to start my blog soon, but I’m a little lost on everything. Would you suggest starting with a free platform like Word Press or go for a paid option? There are so many choices out there that I’m completely confused. Any suggestions? Thanks a lot.
ReplyDeleteAWS Training in Marathahalli | AWS Training in Marathahalli
AWS Amazon Web Services Training in Chennai | Best AWS Training and Certification for Solution Architect in Chennai
Amazon Web Services Training in Chennai |Best AWS Training in Chennai
I’m planning to start my blog soon, but I’m a little lost on everything. Would you suggest starting with a free platform like Word Press or go for a paid option? There are so many choices out there that I’m completely confused. Any suggestions? Thanks a lot.
ReplyDeleteAWS Training in Marathahalli | AWS Training in Marathahalli
AWS Amazon Web Services Training in Chennai | Best AWS Training and Certification for Solution Architect in Chennai
Amazon Web Services Training in Chennai |Best AWS Training in Chennai
شركة تنظيف كنب بتبوك
ReplyDeleteشركة تنظيف شقق بتبوك
شركة تنظيف خزانات بتبوك
شركة تنظيف سجاد بتبوك
شركة تنظيف منازل بتبوك