# Tag Info

36

Variables I understand why you have the Range.this.end and Range.this.start to avoid confusion about where those variables come from... If you need the Range.this as part of the teaching exercise, then sure. Otherwise, I would recommend three things.... add range as a prefix, even though it is slightly redundant Make them final... one variable per line... (...

23

This code has a bug. Consider merge_intervals([(0, 3), (1, 2)]). This returns [(0, 2)] although it should be [(0, 3)]. This can be solved through new_tup = (b[0], max(b[1], tup[1])) Your code is nice, and implements the simplest thing that works. However, you might want to work on improving your variable names. Neither l, b, or si are very descriptive, and ...

14

The code you have posted is straightforward and basic. Because of this, I'm going to assume you are not super-experienced with Python. I'll make some direct suggestions to go from your current code to a faster version of your code, but I don't expect you'll be able to make the time limit with this structure. See @vnp's answer for how to do that. You wrote: ...

13

Overall, it's pretty good code to learn from. Functionality I like that you've used the inclusive-exclusive convention for the lower and upper bounds, respectively. The rationale for that design would be an interesting discussion topic. I suggest adding a second constructor for convenience: public Range(int end) { this(0, end); } There should ...

11

Because the intervals are already sorted by start time, you can begin the inner loop at j = i + 1 and simplify the if test and drop the call to max: if (intervalj.getStart() < intervali.getEnd()) { hashSet.add(new OverlapCoord(intervalj.getStart(), Math.min(intervali.getEnd(), intervalj.getEnd()))); } However, is ...

11

Thou shall not brute force. There is no reason to maintain the entire list of coin states, much less to perform actual flips. The state is easily recoverable from the sequence of 0 operations. The key observation is that a 0 a b operation is in fact a pair of operations: flip coins from a to the end, and flip coins from b + 1 to the end. This leads to the ...

11

I think the problem authors maybe intended for people to use a data structure that allows for fast queries and updates. You can make it run in $Q\log(N)$ time by using a tree structure. First note that flipping coins in the interval $[l,r)$ is the same as flipping $[0,r)$ and $[0,l)$, so we are reduced to flipping $[0,r)$. The idea is not to ...

10

If you are testing the functionality of your code, you should create unit test. I am referencing this part of your code : public static void main(String[] args) { IntervalSearchTree intervalSearchTree = new IntervalSearchTree(); intervalSearchTree.add(17, 19); intervalSearchTree.add(5, 8); intervalSearchTree.add(21, 24); ...

10

This problem is well suited to an iterable method, rather than one that generates a list: sorted_intervals = sorted(intervals, key=itemgetter(0)) if not sorted_intervals: # no intervals to merge return # low and high represent the bounds of the current run of merges low, high = sorted_intervals[0] for iv in sorted_intervals[1:]: if iv[0] <= ...

10

@Peter Taylor has a good idea, but there is more to be improved You should add some tests Python is often described as Batteries included This is a perfect example to use itertools.groupby() from itertools import groupby import doctest def extract_seq(seq): """ Splits sequence into consecutive lists args: seq (list)...

9

Reading Points you have the method and class: private static List<Point> readPoints(String line) { List<Point> points = new ArrayList<>(); Scanner scanner = new Scanner(line); while (scanner.hasNext()) { int left = scanner.next(); int height = scanner.next(); int right = scanner.next(); points.add(new ...

9

The code looks well presented, and it's clear how it maps to the problem statement. The one thing that's not well defined is how we deal with exact equality of times. I'm assuming that intervals are always half-open (i.e. including the start time, but excluding the end time); it would be wise to add suitable comments to ensure that all readers agree on ...

9

Review You are constrained to float which makes your class only usable for a limited number of scenarios. I would like to be able to work with int, double, DateTime, MyCustomEntity, .. You should not need to care about special cases as unbounded or NaN. NaN should be filtered out beforehand, since it is unusable for comparison. Unbounded and bounded values ...

8

Size of initial list in the following code is less: var x = Enumerable.Range(1, 10) .Select(x_ => x_ * 10) .Concat(new[] {25}) .Distinct() .OrderBy(x_ => x_) .ToList(); Otherwise your original code is perfect.

8

For the most part, this appears to be neat, and well structured. There is a significant bug, though: Iterable<Integer> implies an iterator() method. Each time you call that iterator() method you should get a new instance of an interator, not an 'expired' instance. For example, the following code should print the numbers 1 to 10 twice.... Range ...

8

You could make the Meeting class generic with the T : IComparable<T> constraint. Thus you'll be able to use any type as a time value: [DebuggerDisplay("{Start} .. {End}")] public sealed class Meeting<T> where T : IComparable<T> { // You can replace these readonly fields with the auto-properties { get; private set; }: public ...

8

Your code uses an algorithm that directly tests for an overlap of time spans, but a simpler algorithm is to check for a non-overlap - to check for whether the time-spans are completely distinct. The spans are distinct if the first span starts after the other ends, or ends before the other one starts. This test is easy. The spans overlap if they are not ...

8

Quite frankly it seems that you did not do what was asked from you. The text above assign gives you the requirements // Assign value val to interval [keyBegin, keyEnd). // Overwrite previous values in this interval. // Conforming to the C++ Standard Library conventions, the interval // includes keyBegin, but excludes keyEnd. // If !( ...

8

Don't force a class where a function is perfectly fine. The namespace std is not designed for wholesale importation, see "Why is “using namespace std” considered bad practice?" for more detail. Identifiers starting with an underscore followed by an uppercase letter are reserved. Input is generally unreliable. But you don't test for error at all. Always ...

7

Generally speaking, it's good and works great (version 2 seems better). There are some things that could be changed/added though: In C++, ranges tend to be [begin, end) ranges. Your compile-time integer ranges are actually [begin, end] ranges. The last element should not be included in the range. Therefore, you change this code: template<int S, int E>...

7

@rolfl totally nailed it. Only a few nitpicks left behind: I'd drop all pointless comments, unless they serve a purpose when you teach this Add the @Override annotations for clarity when reading not in an IDE Whenever you can drop this. from this.cursor, I'd drop it The way you use spacing around brackets does not follow well the standard. Use the reformat ...

7

Structure Right now, you can only create a skyline for this one type of input format. To fix this, readPoints shouldn't be part of getSkyline. Instead, getSkyline should accept a list of Point objects (which you created somewhere else, eg main). Output In your problem description it says: printing a list of points (x,h), but you are not formatting it ...

7

Your intersection code only catches cases where a meeting is entirely within the time of another meeting. For example, it will not catch the overlap in 10am-2pm and 1pm-4pm. Instead, its easier to check for non-intersection, and then negate. This is a popular approach to checking for intersection in rectangles. if (!(item.StartTime > other.endTime || ...

7

You have a lot of unnecessary vertical spacing which should be removed to improve readability. Based on the naming guidelines input parameter should be named using camelCase casing. Because WriteToRange() can be called also as a normal static method you need to check both input parameters for null. The storeDictionaryData is basically a object[...

7

Interval Your interval class is neat, well, structured in general. The hashCode/equals/compareTo contracts all look accurate. I like the Java-8-like use of the of(...) factory method. The compareTo method is fine, but, I wonder whether it is better to express that as a Comparator call. Java8 has some nice comparator extensions, you should use them... oh, ...

7

A lot (most) of the methods from the interface are currently throwing an UnsupportedOperationException, either because the operation doesn't make sense (adding to the range), Start with an AbstractList, it already throws UnsupportedOperationException on any mutating operation. Implementing an immutable list is fine, there's one general purpose ...

7

Some style issues: Space before { Spaces around -> Space after , No space before : Space before else Indent else blocks 4 characters Make constructor functions part of the impl: impl Range { fn new(start: i32, end: i32) -> Range { Range { start: start, end: end, } } } Instead of creating a to_string ...

7

Naming Conventions MSDN, General Naming Conventions DO NOT use Hungarian notation: [dt]Start in getPickTimeframe() --> DateTime currentFrameStartDate [dt]End in getPickTimeframe() --> DateTime currentFrameEndDate DO favor readability over brevity: ParkedCar --> ParkingLog getPickTimeframe(List<ParkedCar> [cars]) --> GetPeakTimeFrame(List<...

7

Negating the no-overlap case You mention four separate cases where two time intervals overlap. You then reduce it to three by pointing out that one case is really the intersection of two of the other cases. So checking those cases implicitly checks the fourth. But this is more complicated than it needs to be. Instead of thinking about when they overlap, ...

7

Using yield is often simpler than building up a list to return. Here it would reduce res = [] last = seq while len(last) > 1: first, last = split_sequence(last) res.append(first) if len(last) == 1: res.append(last) return res to last = seq while len(last) > 1: first, last = split_sequence(last) ...

Only top voted, non community-wiki answers of a minimum length are eligible